c++ backtracking trie easy to understand


  • 0
    J
    class Solution {
    private:
        struct TrieNode{
            bool isWord;
            unordered_map<char, TrieNode*> children;
            TrieNode():isWord(false){};
        };
        
        void AddWord(TrieNode* root, string& s){
            TrieNode* cur=root;
            for(auto c:s){
                if(cur && !cur->children.count(c)){
                    cur->children[c]=new TrieNode;
                }
                cur=cur->children[c];
            }
            cur->isWord=true;
        }
        
        int dirx[4]={-1, 0, 1, 0};
        int diry[4]={0, -1, 0, 1};
    public:
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            TrieNode* root=new TrieNode;
            for(auto s:words)
            {
                AddWord(root, s);
            }
            
            int m=board.size();
            int n=m==0?0:board[0].size();
            set<string> ansset;
            vector<string> ans;
            string str;
            
            for(int i=0; i<m; i++)
            {
                for(int j=0; j<n; j++)
                {
                    TrieNode* node=root;
                    help(board, i, j, node, ansset, str);
                }
            }
            for(auto s:ansset)
                ans.push_back(s);
            return ans;
        }
        
        void help(vector<vector<char>>& board, int i, int j, TrieNode* root, set<string>& ans, string& str)
        {
            int m=board.size();
            int n=m==0?0:board[0].size();
            if(i<0 || i>=m || j<0 || j>=n)
                return;
            
            char c=board[i][j];
            if(root &&  root->children.count(c))
            {
                
                for(int k=0; k<4; k++)
                {
                    board[i][j]=' ';
                    i=i+dirx[k];
                    j=j+diry[k];
                    str.push_back(c);
                    if(root->children[c]->isWord==true){
                        ans.insert(str);
                       
                    }
                    help(board, i, j, root->children[c], ans, str);
                    str.pop_back();
                    i=i-dirx[k];
                    j=j-diry[k];
                    board[i][j]=c;
                }
            }
        }
    };
    

Log in to reply
 

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