Leetcode-212-Word Search II

这题我一开始觉得就是一个简单的dfs，只需要先建立board中各个字母到其坐标的映射，使得我们搜索words时可以知道从何处开始搜索即可。不过这题的数据比较苛刻，最终36个数据点只过了34个，有两个大数据TLE了。

看了下解答，又学到一个新的数据结构Tire（字典树），在此简要记录一下。

Trie，字典树，又称单词查找树、前缀树，是一种哈希树的变种。应用于字符串的统计与排序，经常被搜索引擎系统用于文本词频统计。

性质：

1.根节点不包含字符，除根节点外的每一个节点都只包含一个字符。

2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

3.每个节点的所有子节点包含的字符都不相同。

优点是查询快。对于长度为m的键值，最坏情况下只需花费O(m)的时间。

本题解法中第一部分即为字典树的构造（https://leetcode.com/problems/word-search-ii/discuss/59841/My-AC-very-clean-C%2B%2B-code）

class TrieNode{
public:
    bool is_end;
    vector<TrieNode*> children;
    TrieNode(){
        is_end=false;
        children=vector<TrieNode*>(26, NULL);
    }   
};

class Trie{
public:
    TrieNode* getRoot(){return root;}
    Trie(vector<string>& words){
        root=new TrieNode();
        for(int i=0; i<words.size(); ++i)
            addWord(words[i]);
    }
    void addWord(const string& word){
        TrieNode* cur=root;
        for(int i=0; i<word.size(); ++i){
            int index=word[i]-'a';
            if(cur->children[index]==NULL)   
               cur->children[index]=new TrieNode();
            cur=cur->children[index];    
        }
        cur->is_end=true;
    }
private:
    TrieNode* root;
};

构造好字典树Trie类之后，我们就可以遍历board，以其中每个位置为起点使用Trie进行查找了：

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Trie* trie = new Trie(words);
        TrieNode* root=trie->getRoot();
        set<string> result_set;
        for(int x=0; x<board.size(); ++x)
            for(int y=0; y<board[0].size(); ++y)
                findWords(board, x, y, root, "", result_set);
        
        vector<string> result;
        for(auto it:result_set)    result.push_back(it);
        return result;        
    }
private:
    void findWords(vector<vector<char>>& board, int x, int y, TrieNode* root, string word, set<string>& result){
        if(x<0||x>=board.size()||y<0||y>=board[0].size() || board[x][y]==' ') return;
        
        if(root->children[board[x][y]-'a'] != NULL){
            word=word+board[x][y];
            root=root->children[board[x][y]-'a']; 
            if(root->is_end) result.insert(word);
            char c=board[x][y];
            board[x][y]=' ';
            findWords(board, x+1, y, root, word, result);
            findWords(board, x-1, y, root, word, result);
            findWords(board, x, y+1, root, word, result);
            findWords(board, x, y-1, root, word, result);
            board[x][y]=c;
        }
    }
};