C++ Trie + DFS solution


  • 0
    W

    C++ Trie + DFS solution.

    struct TrieNode {
        TrieNode() : isEnd(false) {}
    
        bool isEnd;
        map<char, TrieNode *> childNodes;
    };
    
    class Solution {
    public:
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            root = new TrieNode();
            for (string word : words) {
                insertWords(word);
            }
    
            unordered_set<string> res;
            if (board.empty() || board[0].empty()) {
                return vector<string>();
            }
    
            int m = board.size(), n = board[0].size();
            vector<char> path;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    dfsSearch(board, path, res, i, j, root, m, n);
                }
            }
    
            return vector<string>(res.begin(), res.end());
        }
    
    private:
        TrieNode * root;
    
        void dfsSearch(vector<vector<char>>& board, vector<char>& path, unordered_set<string>& res, int curR, int curC, TrieNode * node, int m, int n) {
            if (curR < 0 || curR >= m || curC < 0 || curC >= n || board[curR][curC] == '0')
                return;
    
            if (node->childNodes.find(board[curR][curC]) == node->childNodes.end()) {
                return;
            }
    
            char tmp = board[curR][curC];
            path.push_back(tmp);
    
            if (node->childNodes[board[curR][curC]]->isEnd) {
                res.insert(string(path.begin(), path.end()));
            }
    
            board[curR][curC] = '0';
            dfsSearch(board, path, res, curR + 1, curC, node->childNodes[tmp], m, n);
            dfsSearch(board, path, res, curR, curC + 1, node->childNodes[tmp], m, n);
            dfsSearch(board, path, res, curR - 1, curC, node->childNodes[tmp], m, n);
            dfsSearch(board, path, res, curR, curC - 1, node->childNodes[tmp], m, n);
    
            board[curR][curC] = tmp;
            path.pop_back();
        }
    
        void insertWords(string word) {
            TrieNode* curNode = root;
            for (int i = 0; i < word.size(); i++) {
                if (curNode->childNodes.find(word[i]) == curNode->childNodes.end()) {
                    curNode->childNodes[word[i]] = new TrieNode();
                }
    
                curNode = curNode->childNodes[word[i]];
            }
            curNode->isEnd = true;
        }
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.