C++ Trie sol


  • 0
    M
    1. Each TrieNode contains 26 children TrieNode (initialized to NULL, not NULL only if this char exists) and a bool indicating if itself is a word end char
    
    2. Building a word into the Trie takes linear time (word length)
    
    3. When searching a word down the Trie, keep a bool "modified". That is, if you have modified one char already, mark it as true and then go down the Trie. Once a char has been modified, all the chars following it must match the Trie when going downward. On the other hand, if no char has ever been modified, all children nodes that are not NULL are candidates.
      
    
    struct TrieNode {
        TrieNode():children(vector<TrieNode*>(26,NULL)),end(false) {}
        ~TrieNode() {
            for(auto& node:children) if(!node) delete node;
        }
        vector<TrieNode*> children;
        bool end;
    };
    
    class MagicDictionary {
    public:
        /** Initialize your data structure here. */
        MagicDictionary():root(new TrieNode()) {}
        
        /** Build a dictionary through a list of words */
        void buildDict(vector<string> dict) {
            for(const auto& word:dict) 
                buildOneWord(root,word,0);
        }
        
        /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
        bool search(string word) {
            return search(word,0,root,false);
        }
    private:
        TrieNode* root;
        
        void buildOneWord(TrieNode* root, const string& word, int i) {
            if(!root || i==word.length()) return;
            int k=word[i]-'a';
            
            if(!root->children[k]) root->children[k] = new TrieNode();
            if(i==word.length()-1) root->children[k]->end=true;
            buildOneWord(root->children[k],word,i+1);
        }
        
        bool search(const string& word, int i, const TrieNode* root, bool modified) {
            if(!root || i==word.length()) return false;
            int k = word[i]-'a';
            
            if(modified) {
                if(root->children[k]) {
                    if(i==word.length()-1 && root->children[k]->end) return true; //term. cond.
                    return search(word,i+1,root->children[k],modified);
                }
            }
            else {
                for(int j=0; j<26; j++) {
                    if(!root->children[j]) continue;
                    if(i==word.length()-1 && j!=k && root->children[j]->end) return true; // term. cond.
                    if(j==k) {
                        if(search(word,i+1,root->children[j],false)) return true;
                    }
                    else {
                        if(search(word,i+1,root->children[j],true)) return true;
                    }
                }
            }
            return false;
        }
    };
    

Log in to reply
 

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