A detailed explanation C++ solution (Trie + backtracking)


  • 0
    G
    class Solution {
    public:
    
        //
        // The Trie Node structure 
        //
        
        struct TrieNode
        {
            TrieNode *Nodes[26];
            string Word;
            
            TrieNode()
            {
                memset(&Nodes,0,sizeof(Nodes));
            }
        } *Root;
        
        //
        // Adds a word to the Trie by iteratively looking
        // at each character of the word and creating a new Node
        // for it, if it doesn't exist
        //
        void AddWord(const string& str)
        {
            TrieNode *Curr = Root;
            
            for(auto &c : str)
            {
                if(Curr->Nodes[c - 'a'] == NULL)
                {
                    Curr->Nodes[c - 'a'] = new TrieNode;
                }
                
                Curr = Curr->Nodes[c - 'a'];
            }
            
            Curr->Word = str;
        }
        
    
        Solution()
        :
        Root(new TrieNode)
        {
        }
        
        //
        // This is the DFS main function
        //
        
        void Visit(vector<vector<char>>& board,int i, int j, TrieNode *R, unordered_set<int> &Visited,unordered_set<string> &Res)
        {
            static vector<pair<int,int>> Dir = {{-1,0},{1,0},{0,-1},{0,1}};
            
            //
            // If the TrieNode is NULL bail out
            //
            if(R == NULL)
            {
                return;
            }
            
            //
            // if we reached a leaf node of the trie,
            // add the word to the Res set but continue 
            // looking as there might be more words that have this current
            // word as a prefix.
            //
            
            if(R->Word.empty() == false)
            {
                Res.insert(R->Word);
                R->Word.clear();
            }
            
            //
            // check all 4 directions of this current board location
            // if they are in bound and we have not visited them during this
            // current traversal (we don't want loops) add them to the visited
            // set and recusively visit them.
            // when we return from the recursion we need to remove them from the 
            // visited set so that they may be traversed from a different path.
            //
            
            for(auto &P : Dir)
            {
                int Ni = i + P.first;
                int Nj = j + P.second;
                
                if(Ni >= 0 && Ni < board.size() && Nj >= 0 && Nj < board[Ni].size())
                {
                    int V = Ni*(board[Ni].size()) + Nj;
                    
                    if(Visited.find(V) == Visited.end())
                    {
                        Visited.insert(V);
                        Visit(board,Ni,Nj,R->Nodes[board[Ni][Nj] - 'a'],Visited,Res);
                        Visited.erase(V);
                    }
                }
            }
        }
    
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) 
        {
            //
            // Add the words from the dictionary to the Trie
            //
            for(auto &s : words)
            {
                AddWord(s);
            }
            
            //
            // We'll store the words we locate in a set
            // so that we will avoid duplicates
            //
            
            unordered_set<string> Res;
            
            for(int i = 0; i < board.size(); ++i)
            {
                for(int j = 0; j < board[0].size(); ++j)
                {
                    unordered_set<int> Visited;
                    Visited.insert(i*board[0].size() + j);
                    Visit(board,i,j,Root->Nodes[board[i][j] - 'a'],Visited,Res);
                }
            }
            
            return (vector<string>(Res.begin(),Res.end()));
        }
    };

Log in to reply
 

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