Word Search I 用基本的DFS就可以做出，由于僅找一個單詞，難度不高。
而Word Search II 是要找一系列的單詞。對DFS的難度增大不少。

II的要點是：

1. 用Trie來建立需要尋找的單詞數(shù)組
2. 在DFS時，一定要先判斷TrieNode->mp[char] 是否存在，如果存在進而拿到下一個TrieNode。不存在則return，要先拿到TrieNode，再進入下一個DFS loop
3. 用set<string> 記錄string，避免重復。而且當拿到一個string時，不能返回！因為還有可能要繼續(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}};
};