212.单词搜索 II (Hard)*

class TrieNode {
public:
    string str;
    unordered_map<char, TrieNode*> next;
    TrieNode() : str("") {}
};
class Solution {
private:
    vector<string> res;
    int m, n;
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        if(board.size() == 0 || board[0].size() == 0 || words.size() == 0) {
            return {};
        }
        TrieNode* root = new TrieNode();
        // 构造前缀树
        auto cur = root;
        for(auto& word : words) {
            cur = root;
            for(auto& c : word) {
                if(!cur->next.count(c)) {
                    cur->next[c] = new TrieNode();
                }
                cur = cur->next[c];
            }
            cur->str = word;
        }
        m = board.size(), n = board[0].size();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                dfs(board, root, i, j);
            }
        }
        return res;
    }
    void dfs(vector<vector<char>>& board, TrieNode* cur, int i, int j) {
        if(cur->str != "") {
            res.push_back(cur->str);
            cur->str = "";
            return;
        }
        if(i >= m || j >= n || i < 0 || j < 0 || !cur->next.count(board[i][j])) {
            return;
        }
        cur = cur->next[board[i][j]];
        board[i][j] ^= 128;
        dfs(board, cur, i + 1, j); 
        dfs(board, cur, i - 1, j);
        dfs(board, cur, i, j + 1);
        dfs(board, cur, i, j - 1);
        board[i][j] ^= 128;
    }
};