leetcode212 单词搜索II

题目

单词搜索II

暴力解法

暴力解法就是用leetcode79 单词搜索这题的搜索一个单词的dfs方法，挨个搜索每个单词。

字典树

• 将所有单词构造成一颗字典树，每一个节点加一个是否是叶子的标记位
• dfs来搜索这个字典树
  注意：搜到一个单词节点的时候，不要返回。因为有可能这种情况：["abc"，"abcd"]。

字典树代码

struct MyTreeNode{
    int is_leaf;
    MyTreeNode* children[26];

    MyTreeNode() {
        is_leaf = 0;
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};

class Solution {
private:
    MyTreeNode *root[26];
    vector<string> res;
    int row;
    int col;

    void dfs_for_create_tree(int k, string& str, MyTreeNode* &cur_root) {
        if (cur_root == nullptr) {
            cur_root = new MyTreeNode();
        } 
        if (k == str.size() - 1) {
            cur_root->is_leaf++;
        }

        if (k + 1 < str.size()){
            dfs_for_create_tree(k + 1, str, cur_root->children[str[k + 1] - 'a']);
        }
    }

    void dfs_for_searh_tree(int cur_i, int cur_j, string cur_s, MyTreeNode* &cur_root, vector<vector<char>>& board) {
        if (cur_root == nullptr) {
            return;
        }

        if (cur_root->is_leaf) {
            res.push_back(cur_s);
            cur_root->is_leaf--;
        }

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

        char ch = board[cur_i][cur_j];
        board[cur_i][cur_j] = '1';

        for (int i = 0; i < 4; i++) {
            int next_i = cur_i + next[i][0];
            int next_j = cur_j + next[i][1];

            if (next_i < 0 || next_i >= row || next_j < 0 || next_j >= col) {
                continue;
            }

            char next_ch = board[next_i][next_j];
            if (next_ch == '1') {
                continue;
            }

            dfs_for_searh_tree(next_i, next_j, cur_s + next_ch, cur_root->children[next_ch - 'a'], board);        
        }
        board[cur_i][cur_j] = ch;
    }
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        if (board.empty()) {
            return {};
        }

        for (auto & str : words) {
            dfs_for_create_tree(0, str, root[str[0] - 'a']);
        }
        
        row = board.size();
        col = board[0].size();

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                string s;
                s += board[i][j];
                dfs_for_searh_tree(i, j, s, root[board[i][j] - 'a'], board);
            }
        }

        return res;
    }
};