C++ solution with dfs and trie


  • 0
    X
    class Solution {
    private:
        class TrieNode {
        public:
            // Initialize your data structure here.
            TrieNode() {
                for(int i = 0; i < 26; i++)
                    next[i] = NULL;
                isString = false;
            }
            TrieNode *next[26];
            bool isString;
        };
        TrieNode* root;
        int M, N;
    
    public:
        // Inserts a word into the trie.
        void insert(string word) {
            TrieNode *p = root;
            for(int i = 0; i < word.size(); i++){
                if(p->next[word[i]-'a'] == NULL){
                    p->next[word[i]-'a'] = new TrieNode();
                }
                p = p->next[word[i]-'a'];
            }
            p->isString = true;
        }
     
        void dfs(vector<vector<char>>& board, vector<vector<bool>>& visit, int i, int j,
                 string word, TrieNode* current, set<string> &res) {
            if (i < 0 || i >= M || j < 0 || j >= N)
                return;
            if (visit[i][j])
                return;
            char d = board[i][j];
            if (current->next[d-'a'] == NULL)
                return;
            else if (current->next[d-'a']->isString)
            {
                word.push_back(d);
                res.insert(word);
                current = current->next[d-'a'];
            }
            else
            {
                word.push_back(d);
                current = current->next[d-'a'];
            }
            visit[i][j] = 1;
            dfs(board, visit, i+1, j, word, current, res);
            dfs(board, visit, i, j+1, word, current, res);
            dfs(board, visit, i-1, j, word, current, res);
            dfs(board, visit, i, j-1, word, current, res);
            visit[i][j] = 0;
        }
        
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            M = board.size();
            N = board[0].size();
            root = new TrieNode();
            for (auto w : words)
                insert(w);
            set<string> res;
            vector<vector<bool>> visit(M, vector<bool>(N, 0));
            for (int i = 0; i < M; i ++)
                for (int j = 0; j < N; j ++)
                {
                    TrieNode* current = root;
                    dfs(board, visit, i, j, "", current, res);
                }
            vector<string> ret;
            for (auto w : res)
                ret.push_back(w);
            return ret;
        }
    };
    

Log in to reply
 

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