Word Search II (leetcode 212)

Word Search I 用基本的DFS就可以做出，由于仅找一个单词，难度不高。
而Word Search II 是要找一系列的单词。对DFS的难度增大不少。

II的要点是：

1. 用Trie来建立需要寻找的单词数组
2. 在DFS时，一定要先判断TrieNode->mp[char] 是否存在，如果存在进而拿到下一个TrieNode。不存在则return，要先拿到TrieNode，再进入下一个DFS loop
3. 用set<string> 记录string，避免重复。而且当拿到一个string时，不能返回！因为还有可能要继续搜索.

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}};
};