Word Search I 用基本的DFS就可以做出，由于僅找一個(gè)單詞躯畴，難度不高刨晴。
而Word Search II 是要找一系列的單詞。對DFS的難度增大不少茫死。

II的要點(diǎn)是：

1. 用Trie來建立需要尋找的單詞數(shù)組
2. 在DFS時(shí)跪但，一定要先判斷TrieNode->mp[char] 是否存在，如果存在進(jìn)而拿到下一個(gè)TrieNode峦萎。不存在則return屡久，要先拿到TrieNode，再進(jìn)入下一個(gè)DFS loop
3. 用set<string> 記錄string爱榔，避免重復(fù)被环。而且當(dāng)拿到一個(gè)string時(shí)，不能返回搓蚪！因?yàn)檫€有可能要繼續(xù)搜索.

class TrieNode{
public:
    bool isWord;
    unordered_map<char, TrieNode*> mp;
    TrieNode() : isWord(false){}
};

class Trie{
public:
    Trie(){ root = new TrieNode(); }
    TrieNode *getRoot(){
        return root;
    }
    void insertWord(string cur){
        TrieNode *p = root;
        for(int i=0; i<cur.length(); i++){
            if(!p->mp.count(cur[i])){
                p->mp[cur[i]] = new TrieNode();
            }
            p = p->mp[cur[i]];
        }
        p->isWord = true;
    }
private:
    TrieNode *root;
 
};

class Solution {
public:

    void dfs(vector<vector<char>>& board, set<string> &allcomb, string &comb, vector<vector<bool>> &visited, TrieNode *p, int i, int j){
        
        int row = board.size(), col = board[0].size();
        comb.push_back(board[i][j]);
        visited[i][j] = true;
        if(p->isWord) {allcomb.insert(comb);}
        
        for(auto it : directions){
            int x = i + it.first, y = j + it.second;
            if(x < 0 || x >= row || y < 0 || y >= col || visited[x][y]) continue;
            if(p->mp.count(board[x][y])){
                dfs(board, allcomb, comb, visited, p->mp[board[x][y]], x, y);
            }
        }
        comb.pop_back();
        visited[i][j] = false;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        set<string> allcomb;
        if(board.empty() || board[0].empty()) return vector<string>();
        int row = board.size(), col = board[0].size();
        myTrie = new Trie();
        for(string s : words){
            myTrie->insertWord(s);
        }
        string comb;
        vector<vector<bool>> visited(row, vector<bool>(col, false));
        TrieNode *root = myTrie->getRoot();
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(!root->mp.count(board[i][j])) continue;
                dfs(board, allcomb, comb, visited, root->mp[board[i][j]], i, j);
            }
        }
        return vector<string>(allcomb.begin(), allcomb.end());
    }
private:
    Trie *myTrie;
     vector<pair<int, int>> directions{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
};