212. 单词搜索 II

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例 1：

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

示例 2：

输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] 是一个小写英文字母
• 1 <= words.length <= 3 * 104
• 1 <= words[i].length <= 10
• words[i] 由小写英文字母组成
• words 中的所有字符串互不相同

思路：对字典用Tire树维护，然后遍历网格，在每一个点上进行DFS，网格上的元素遍历与Tire树上遍历同步，若Tire树上不存在对应路径，则直接减枝。

class Solution {
public:

    bool visited[20][20];

    struct TireNode{
        bool is_leaf;
        TireNode* Next[26];
        TireNode(){
            is_leaf = false;
            memset(Next, NULL, sizeof(Next));
        }
    };

    int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    void DFS(int row, int col, int& n, int& m, TireNode* root, vector<vector<char>>& board, unordered_set<string>& str_set, string str){
        //cout << row << " " << col << " " << str << " is_null:" << (root == NULL) << " is_vis:" << visited[row][col] << endl;
        if(!root)return;
        if(root->is_leaf){
            str_set.insert(str);
        }
        int i, x, y;
        for(i = 0; i < 4; ++ i){
            x = dir[i][0] + row;
            y = dir[i][1] + col;
            if(x < 0 || x >= n || y < 0 || y >= m) continue;
            if(!visited[x][y]){
                visited[x][y] = true;
                DFS(x, y, n, m, root->Next[board[x][y] - 'a'], board, str_set, str + string(1, board[x][y]));
                visited[x][y] = false;
            }
        }
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        TireNode *root = new TireNode(), *p;
        int n = board.size(), m = board[0].size(), cnt;
        for(auto word:words){
            p = root;
            for(int index = 0; index < word.size(); ++ index){
                if(p->Next[cnt = word[index] - 'a'] == NULL){
                    p->Next[cnt] = new TireNode();
                }
                p = p->Next[cnt];
                if(index == word.size() - 1){
                    p->is_leaf = true;
                }
            }
        }
        memset(visited, 0, sizeof(visited));
        unordered_set<string> str_set;
        for(int row = 0; row < n; ++ row){
            for(int col = 0; col < m; ++ col){
                visited[row][col] = true;
                DFS(row, col, n, m, root->Next[board[row][col] - 'a'], board, str_set, string(1, board[row][col]));
                visited[row][col] = false;
            }
        }
        vector<string> find_res;
        for(unordered_set<string>::iterator iter = str_set.begin(); iter != str_set.end(); ++ iter){
            find_res.push_back(*iter);
        }
        return find_res;
    }
};

当然，动态开辟空间会比较慢，你也可以选择静态存储池的方案。

class Solution {
public:

    bool visited[20][20];
    static const int pool_size = 3e5 + 7;

    struct TireNode{
        bool is_leaf;
        int Next[26];
        void init(){
            is_leaf = false;
            memset(Next, -1, sizeof(Next));
        }
    };

    TireNode tire_nodes[pool_size];

    int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    void DFS(int row, int col, int& n, int& m, int root, vector<vector<char>>& board, unordered_set<string>& str_set, string str){
        //cout << row << " " << col << " " << str << " is_null:" << (root == NULL) << " is_vis:" << visited[row][col] << endl;
        if(root == -1)return;
        if(tire_nodes[root].is_leaf){
            str_set.insert(str);
        }
        int i, x, y;
        for(i = 0; i < 4; ++ i){
            x = dir[i][0] + row;
            y = dir[i][1] + col;
            if(x < 0 || x >= n || y < 0 || y >= m) continue;
            if(!visited[x][y]){
                visited[x][y] = true;
                DFS(x, y, n, m, tire_nodes[root].Next[board[x][y] - 'a'], board, str_set, str + string(1, board[x][y]));
                visited[x][y] = false;
            }
        }
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        int n = board.size(), m = board[0].size(), cnt = 0, value, root = 0, p;
        tire_nodes[root].init();
        
        for(auto word:words){
            p = root;
            for(int index = 0; index < word.size(); ++ index){
                if(tire_nodes[p].Next[value = word[index] - 'a'] == -1){
                    tire_nodes[p].Next[value] = ++ cnt;
                    tire_nodes[cnt].init();
                }
                p = tire_nodes[p].Next[value];
                if(index == word.size() - 1){
                    tire_nodes[p].is_leaf = true;
                }
            }
        }
        memset(visited, 0, sizeof(visited));
        unordered_set<string> str_set;
        for(int row = 0; row < n; ++ row){
            for(int col = 0; col < m; ++ col){
                visited[row][col] = true;
                DFS(row, col, n, m, tire_nodes[root].Next[board[row][col] - 'a'], board, str_set, string(1, board[row][col]));
                visited[row][col] = false;
            }
        }
        vector<string> find_res;
        for(unordered_set<string>::iterator iter = str_set.begin(); iter != str_set.end(); ++ iter){
            find_res.push_back(*iter);
        }
        return find_res;
    }
};