212 单词搜索 II

https://leetcode.cn/leetbook/read/top-interview-questions-hard/xdpw1v/

cost:

class Node {
public:
    Node(char ch_) : ch(ch_) { children = {}; }
    char ch;
    bool isEnd = false;
    unordered_map<char, Node*> children;
};

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board,
                             vector<string>& words) {
        auto wordDictTree = new Node(0);
        Node* p = nullptr;
        for (const auto& word : words) {
            p = wordDictTree;
            for (const char ch : word) {
                if (!p->children.count(ch)) {
                    p->children[ch] = new Node(ch);
                }
                p = p->children[ch];
            }
            p->isEnd = true;
        }

        visited =
            vector<vector<int>>(board.size(), vector<int>(board[0].size(), 0));
        vector<Node*> vec;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                char ch = board[i][j];
                if (!wordDictTree->children.count(ch)) {
                    continue;
                }
                vec.push_back(wordDictTree);
                this->dfs(board, i, j, vec);
                vec.pop_back();
            }
        }
        vector<string> ans;
        for (const auto& s : this->res) {
            ans.push_back(s);
        }
        return ans;
    }

private:
    void dfs(vector<vector<char>>& board, int i, int j, vector<Node*>& vec) {
        if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() ||
            visited[i][j]) {
            return;
        }
        visited[i][j] = 1;
        auto father = vec.back();
        char ch = board[i][j];
        if (!father->children.count(ch)) {
            visited[i][j] = 0;
            return;
        }
        auto node = father->children[ch];
        if (node->isEnd) {
            string s;
            for (int i = 1; i < vec.size(); i++) {
                s.push_back(vec[i]->ch);
            }
            s.push_back(node->ch);
            res.insert(s);
        }
        vec.push_back(node);
        this->dfs(board, i - 1, j, vec);
        this->dfs(board, i + 1, j, vec);
        this->dfs(board, i, j - 1, vec);
        this->dfs(board, i, j + 1, vec);
        vec.pop_back();
        visited[i][j] = 0;
    }
    unordered_set<string> res;
    vector<vector<int>> visited;
};