###### tags: `LeetCode` `Trie` `Object Oriented` `Tree` `Recursion` `DFS` `Hard`
# LeetCode #212 [Word Search II](https://leetcode.com/problems/word-search-ii/)
### (Hard)

給定一個 m x n 二維字符網格 board 和一個單詞（字符串）列表 words，找出所有同時在二維網格和字典中出現的單詞。

單詞必須按照字母順序，通過 相鄰的單元格 內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母在一個單詞中不允許被重複使用。

---

由於輸入單字長度太長, 使用普通的三個for迴圈呼叫會超時, 因此在遍歷輸入字串方面使用Trie取代for迴圈減少時間複雜度, 有關Trie的建立可以看 [#208](https://hackmd.io/x1QTNKhtR423HF5FKadOPw)。

要建立Trie類別之前, 由於整個Trie樹是由多個TrieNode構成, 因此需要先建立TrieNode類別。由於solution類別需要用到Trie類別, 而Trie類別又需要用到TrieNode類別, 因此順序須按照TrieNode-Trie-Solution排列, 否則會無法辨識。

Trie類別的初始化會接收一個string數組作為參數, 並按照數組內的每一個字串建立字典樹。再透過getRoot函式呼叫可以拿到該字典樹的樹根。

接下來遍歷整個board, 若其中元素(字元-char)存在於字典樹中, 則將該字元存入暫存字串tmp中, 並在該元素的上下左右尋找是否有字元符合字典樹節點接下來的子節點, 並繼續遞迴。

而若經過的字典樹節點TrieNode的is_word值為true, 代表board中存在組合滿足一開始輸入的字串數組中的某個字串, 此時將暫存字串tmp存入答案集合中。如此循環直到尋找到board的邊界, 或是下一個地址的字元已被使用過(使用過的字元會被改成'#')。

使用集合可以避免重複解, 在遍歷完整個board後再把集合中的元素存入數組ans中, 最後回傳ans即可。

---

class TrieNode{
public:
    bool is_word;
    vector<TrieNode*> children;
    TrieNode():is_word(false), children(26, nullptr){}
    ~TrieNode(){
        for(auto c:children)
            if(c)delete c;
    }
};
class Trie{
public:
    TrieNode* root_;
    Trie(vector<string>& word):root_(new TrieNode()){
        for(int i=0;i<word.size();i++)
            insert(word[i]);
    }
    
    TrieNode* getRoot(){
        return root_;
    }
    void insert(const string& s){
        TrieNode* p = root_;
        for(auto c:s){
            if(!p->children[c-'a'])
                p->children[c-'a']=new TrieNode();
            p=p->children[c-'a'];
        }
        p->is_word = true;
    }
};
class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> ans;
        set<string> tmp;
        Trie* trie = new Trie(words);
        TrieNode* root = trie->getRoot();
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                dfs(board, i, j, root, "", tmp);
            }
        }
        for(auto s:tmp)ans.push_back(s);
        return ans;
    }
private:
    void dfs(vector<vector<char>>& board, int i, int j, TrieNode* root, string word, set<string>& tmp){
        if(i<0||j<0||i>=board.size()||j>=board[0].size()||board[i][j]=='#')return;
        if(root->children[board[i][j]-'a']){
            word+=board[i][j];
            root=root->children[board[i][j]-'a'];
            if(root->is_word)tmp.insert(word);
            char c = board[i][j];
            board[i][j] = '#';
            dfs(board, i-1, j, root, word, tmp);//up
            dfs(board, i, j+1, root, word, tmp);//right
            dfs(board, i+1, j, root, word, tmp);//down
            dfs(board, i, j-1, root, word, tmp);//left
            board[i][j]=c;
        }
    }
};

---

沒有使用Trie的暴力法, 會觸發Time Limit Exceeded

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> ans;
        vector<vector<int>> used(board.size(), vector<int>(board[0].size(), 0));
        for(string s:words){
            vector<vector<int>> use(used.begin(), used.end());
            for(int i=0;i<board.size();i++){
                for(int j=0;j<board[0].size();j++){
                    dfs(board, s, i, j, 0, use, ans);
                }
            }
        }
        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
        return ans;
    }
    bool dfs(vector<vector<char>>& board, string word, int i, int j, int pos, vector<vector<int>>& use, vector<string>& ans){
        if(use[i][j]==0&&board[i][j]==word[pos]&&pos==word.size()-1){
            ans.push_back(word);
            return true;
        } 
        else if(use[i][j]==0&&board[i][j]==word[pos]){
            use[i][j]=1;
            if(i==0?false:dfs(board, word, i-1, j, pos+1, use, ans))return true;
            else if(j==board[0].size()-1?false:dfs(board, word, i, j+1, pos+1, use, ans))return true;
            else if(i==board.size()-1?false:dfs(board, word, i+1, j, pos+1, use, ans))return true;
            else if(j==0?false:dfs(board, word, i, j-1, pos+1, use, ans))return true;
            use[i][j]=0;
        }  
        return false;
    }
};