leetcode212_字典树

水一篇文章。最近项目里在用字典树配合redis做搜索和字符串匹配，这部分不是我做的，但为了熟悉一下练练手，刷一道关于字典树的题目。
纠结要不要把刷leetcode的题目搬上来，想想还是放上来吧，毕竟这题只有16%的通过率。况且字典树这个东西以后还是会经常用得到的，算是给自己以后留个参考吧。

题目地址

• Word Search II

字典树、回溯法
我觉得这题主要还是字典树。当然说回溯法也可以，毕竟在搜索的时候根据情况，适时停止，进入下一个分支。不过我觉得更合适的说法是在dfs中增加了条件判断而已。
要说最经典的回溯问题，据我近两年的刷题经验来看，当属 八皇后 问题了，八皇后在leetcode中也有。

这题一入手就用dfs是显然的，从board上每个点开始，作dfs搜索。如何使用words，就是关键所在了。
如果根据每一个词去遍历，显然太慢了，而且会有好多重复的计算，比如两个字abcde,和abcdef有相同的前缀。而用字典树就恰当好处了。

下面是代码：

class Solution {
public:
    class TireNode{
    public:
        TireNode(string p):prefix(p){
            memset(next, 0, sizeof(next));
        };
        bool isEnd = false;
        TireNode* next[26];
        string prefix;
    };

    class Tire{
    public:
        Tire(){
            root = new TireNode("");
        }

        void addString(string s){
            TireNode *cur = root;
            string prefix = "";
            for (auto c : s){
                prefix += c;
                if (cur->next[c - 'a'] == NULL)
                    cur->next[c - 'a'] = new TireNode(prefix);
                cur = cur->next[c - 'a'];
            }
            cur->isEnd = true;
        }

        TireNode *root;
    };

    void dfs(vector<vector<char>>& board, int x, int y, TireNode* cur, vector<string>& ret){
        if (x < 0 || x >= board.size()) return;
        if (y < 0 || y >= board[0].size()) return;
        if (board[x][y] == '*') return;
        char c = board[x][y];
        if (cur == NULL || cur->next[c - 'a'] == NULL) return;
        if (cur->next[c - 'a']->isEnd){
            cur->next[c - 'a']->isEnd = false;
            ret.push_back(cur->next[c - 'a']->prefix);
        }
        board[x][y] = '*';
        dfs(board, x + 1, y, cur->next[c - 'a'], ret);
        dfs(board, x - 1, y, cur->next[c - 'a'], ret);
        dfs(board, x, y + 1, cur->next[c - 'a'], ret);
        dfs(board, x, y - 1, cur->next[c - 'a'], ret);
        board[x][y] = c;
    };

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> ret;
        if (board.size() == 0 || board[0].size() == 0) return ret;

        Tire tire = Tire();
        for (auto s : words){
            tire.addString(s);
        }

        for (int i = 0; i < board.size(); ++i){
            for (int j = 0; j < board[0].size(); ++j){
                dfs(board, i, j, tire.root, ret);
            }
        }

        return ret;
    }
};