212. Word Search II

Trie+backtracking
把字典先转成trie树，然后利用trie树来dfs遍历board

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        if (board.empty() || board[0].empty()) return {};
        TrieNode *root = new TrieNode;
        for (const auto &w : words) {
            insert(root, w);
        }
        vector<string> res;
        int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                dfs(root, board, i, j, dy, dx, res);
            }
        }
        return res;
    }

    struct TrieNode {
        TrieNode *children[26] = {nullptr};
        string w; // 这里存单词，空间换时间
    };

    void insert(TrieNode *p, const string &word) {
        for (char c : word) {
            if (!p->children[c - 'a']) {
                p->children[c - 'a'] = new TrieNode;
            }
            p = p->children[c - 'a'];
        }
        p->w = word;
    }

    // p是当前TrieNode，board[i][j]是下一个字符，要检查的就是p的children里有没有board[i][j]
    void dfs(TrieNode *p, vector<vector<char>> &board, int i, int j, int dy[], int dx[], vector<string> &res) {
        if (i < 0 || j < 0 || i == board.size() || j == board[0].size() || board[i][j] == '#' || !p->children[board[i][j] - 'a']) return;
        char c = board[i][j];
        p = p->children[c - 'a'];
        if (!p->w.empty()) {
            res.push_back(p->w);
            p->w.clear(); // 这里一定要清空，因为board里面一个单词可能会有多个occurrence，为了防止反复找到该单词后添加到答案里，找到以后就改成false，这样下次即便再找到了也不会再往答案里添加了，另外这里不能返回，要继续找，有可能前缀会被复用
        }
        board[i][j] = '#';
        for (int k = 0; k < 4; ++k) {
            dfs(p, board, i + dy[k], j + dx[k], dy, dx, res);
        }
        board[i][j] = c;
    }
};

class Solution {
public:
    struct TrieNode {
        TrieNode *children[26] = {nullptr};
        string w;
    };
    TrieNode *root = nullptr;
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        if (board.empty() || board[0].empty() || words.empty()) return {};
        m = board.size(), n = board[0].size();
        root = new TrieNode;
        for (auto &w : words) {
            insert(w);
        }
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                dfs(board, r, c, root);
            }
        }
        return res;
    }

    void dfs(vector<vector<char>>& board, int r, int c, TrieNode *p) {
        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] == '#' || !p->children[board[r][c] - 'a']) return;
        char ch = board[r][c];
        p = p->children[ch - 'a'];
        if (!p->w.empty()) {
            res.push_back(p->w);
            p->w.clear();
        }
        board[r][c] = '#';
        dfs(board, r + 1, c, p);
        dfs(board, r - 1, c, p);
        dfs(board, r, c + 1, p);
        dfs(board, r, c - 1, p);
        board[r][c] = ch;
    }

    void insert(const string &s) {
        auto p = root;
        for (char c : s) {
            if (!p->children[c - 'a']) {
                p->children[c - 'a'] = new TrieNode;
            }
            p = p->children[c - 'a'];
        }
        p->w = s;
    }

    int m, n;
    vector<string> res;
};