80ms Clear C++ Code with Detailed Explanations


  • 52

    This problem is an application of the Trie data structure. In the following, it is assumed that you have solved Implement Trie (Prefix Tree).

    Now, let's first look at the TrieNode class. I define it as follows.

    class TrieNode {
    public:
        bool isKey;
        TrieNode* children[26];
        TrieNode(): isKey(false) {
            memset(children, NULL, sizeof(TrieNode*) * 26); 
        }
    };
    

    The field isKey is to label whether the string comprised of characters starting from root to the current node is a key (word that has been added). In this problem, only lower-case letters a - z need to be considered, so each TrieNode has at most 26 children. I store it in an array of TrieNode*: children[i] corresponds to letter 'a' + i. The remaining code defines the constructor of the TrieNode class.

    Adding a word can be done in the same way as in Implement Trie (Prefix Tree). The basic idea is to create a TrieNode corresponding to each letter in the word. When we are done, label the last node to be a key (set isKey = true). The code is as follows.

    void addWord(string word) {
        TrieNode* run = root;
        for (char c : word) {
            if (!(run -> children[c - 'a']))
                run -> children[c - 'a'] = new TrieNode();
            run = run -> children[c - 'a']; 
        }
        run -> isKey = true;
    }
    

    By the way, root is defined as private data of WordDictionary:

    private:
        TrieNode* root;
    

    And the WordDictionary class has a constructor to initialize root:

    WordDictionary() {
        root = new TrieNode();
    }
    

    Now we are left only with search. Let's do it. The basic idea is still the same as typical search operations in a Trie. The critical part is how to deal with the dots .. Well, my solution is very naive in this place. Each time when we reach a ., just traverse all the children of the current node and recursively search the remaining substring in word starting from that children. So I define a helper function query for search that takes in a string and a starting node. And the initial call to query is like query(word, root).

    By the way, I pass a char* instead of string to query and it greatly speeds up the code. So the initial call to query is actually query(word.c_str(), root).

    Now I put all the codes together below. Hope it to be useful!

    class TrieNode {
    public:
        bool isKey;
        TrieNode* children[26];
        TrieNode(): isKey(false) {
            memset(children, NULL, sizeof(TrieNode*) * 26);
        }
    };
    
    class WordDictionary {
    public:
        WordDictionary() {
            root = new TrieNode();
        }
    
        // Adds a word into the data structure.
        void addWord(string word) {
            TrieNode* run = root;
            for (char c : word) {
                if (!(run -> children[c - 'a'])) 
                    run -> children[c - 'a'] = new TrieNode();
                run = run -> children[c - 'a'];
            }
            run -> isKey = true;
        }
    
        // Returns if the word is in the data structure. A word could
        // contain the dot character '.' to represent any one letter.
        bool search(string word) {
            return query(word.c_str(), root);
        }
    
    private:
        TrieNode* root;
    
        bool query(const char* word, TrieNode* node) {
            TrieNode* run = node;
            for (int i = 0; word[i]; i++) {
                if (run && word[i] != '.')
                    run = run -> children[word[i] - 'a'];
                else if (run && word[i] == '.') { 
                    TrieNode* tmp = run;
                    for (int j = 0; j < 26; j++) {
                        run = tmp -> children[j];
                        if (query(word + i + 1, run))
                            return true;
                    }
                }
                else break;
            }
            return run && run -> isKey; 
        }
    };
    
    // Your WordDictionary object will be instantiated and called as such:
    // WordDictionary wordDictionary;
    // wordDictionary.addWord("word");
    // wordDictionary.search("pattern");  
    

  • 3
    M

    Good solution! Change your code and use this to construct TrieNode, get 76ms.

    TrieNode(): isKey(false){
        memset(children, NULL, sizeof(TrieNode*)*26);
    }

  • 0
    Z

    good,but it's difficult to understand


  • 0
    N

    In the branch of if (run && word[i] == '.'), if all searchHelper(word + i + 1, run) return false, we can return false directly as we have tested all the conditions.


  • 0

    Hi, mingjun. Thank you for your suggestion. I have updated my code :-)


  • 0

    Hi, novostary. You are right. Thank you for your ideas :-)


  • 0
    O

    ha, as long as I open the thread, I know that it's your post~You always organize your solution clearly! Thanks a lot! Btw, how do you make the red word in the forum editor?


  • 0

    Hi, chungyushao. For the red word, I think you mean red word, right? It is easy, just to quote your words using `. Or you can select your words and click the { } button.


  • 0
    A

    I am asking questions here:

    use TrieNode of unordered_map<char, TrieNode*> as it's member, is much slower than use child[26]. This dose not make sense to me. Child[26] will grow exponentially especially at the bottom (see wiki), while hashing uses much less nodes.

    Another question is that if DFS travel faster than BFS?


  • 0
    This post is deleted!

  • 0
    C

    Hi @jianchao-li-fighter, I was wondering if it is possible to take care of '.' when we build the trie, before we search the word, is it gonna make the algorithm faster?


  • 5
    W

    Here is a shorter and neater solution:

    class TrieNode {
    public:
        TrieNode *next[26]{};
        bool is_leaf = false;
        TrieNode *get(char c) { return next[c - 'a']; }
        void add(char c) { next[c - 'a'] = new TrieNode; }
    };
    
    class WordDictionary {
    public:
        WordDictionary() : root(new TrieNode) {}
        void addWord(const string &word) {
            auto p = root;
            for (auto c : word) {
                if (!p->get(c)) p->add(c);
                p = p->get(c);
            }
            p->is_leaf = true;
        }
        bool search(const string &word) {  return search(word, 0, root); }
    private:
        bool search(const string &word, int pos, TrieNode *root) {
            if (pos == word.size()) return root->is_leaf;
            if (word[pos] != '.') {
                root = root->get(word[pos]);
                return root ? search(word, pos + 1, root) : false;
            }
            for (auto i = 0; i < 26; ++i)
                if (root->next[i] && search(word, pos + 1, root->next[i]))
                    return true;
            return false;
        }
        TrieNode *root;
    };
    

  • 0
    Y

    Add shared_ptr version for reference here.
    I meet MLE issue by using shared pointer;

    Replace it with raw pointer then it works.

    class TrieNode {
    public:
        typedef std::shared_ptr<TrieNode> TrieNodePtr;
        explicit TrieNode(const char c = ' ') : m_char(c),
            m_is_end(false),
            m_children(26,nullptr){}
    private:
        friend class Trie; // set Trie as friend class
        char m_char;
        bool m_is_end;
        std::vector<TrieNodePtr> m_children;
    };
    
    class Trie {
    public:
        Trie() : m_root(new TrieNode()){
        }
    
        // Inserts a word into the trie.
        void insert(const string & word) {
            TrieNode::TrieNodePtr curr = m_root;
            for (auto ch : word) {
                int index = ch - 'a';
                if( !curr->m_children[index] ) {
                    curr->m_children[index] = std::shared_ptr<TrieNode>(new TrieNode(ch) );
                }
                curr = curr->m_children[index];
            }
            curr->m_is_end = true; // means one word end here
        }
       
        bool search(const string & word) const {
            return search(word,0,m_root);   
        }
        
    private:
        bool search(const string & word,int pos,TrieNode::TrieNodePtr node) const {
            if (pos == word.size()) return node && node->m_is_end;
            if (word[pos] == '.') {
                for(const TrieNode::TrieNodePtr & child : node->m_children) {
                    if (child && search(word,pos+1,child)) return true;
                }
                return false;
            } else {
                node = node->m_children[ word[pos]-'a'];
                return node && search(word,pos+1,node);
            }
        }
        
        TrieNode::TrieNodePtr m_root;
    };
    
    class WordDictionary {
    public:
        WordDictionary(){}
        // Adds a word into the data structure.
        void addWord(const string & word) {
            m_trie.insert(word);
        }
    
        // Returns if the word is in the data structure. A word could
        // contain the dot character '.' to represent any one letter.
        bool search(string word){
            return m_trie.search(word);
        }
    private:
        Trie m_trie;
    };
    

  • 0
    L

    @jianchao.li.fighter Hello, thanks for your neat solution and your clear explanations! I have one more question: in the query function, you have a section like this:

    TrieNode* tmp = run;
    for (int j = 0; j < 26; j++) {
         run = tmp -> children[j];
         if (query(word + i + 1, run))
              return true;
    }
    
    If I change it to the following:
    
    for (int j = 0; j < 26; j++) {
         if (query(word + i + 1, run->children[j]))
              return true;
    }
    
    The code does not work anymore, why is that? Thanks in advance!

  • 0
    R

    @liuyuyingufo Yeah, I encountered the same problem. I don't see there is any difference between the two cases, but the latter case failed to pass. Really weird.


  • 0
    M

    I have a doubt. I tried the following changes(which should mean the same) in your code and it gave me wrong answer. could you please tell me why ?
    below is a part of the bool query function
    else if (run && word[i] == '.') {
    TrieNode* tmp;
    for (int j = 0; j < 26; j++) {
    tmp = run -> children[j];
    if (query(word + i + 1, tmp))
    return true;
    }
    }


  • 0
    B

    C++ solution with 66ms
    class WordDictionary {
    public:
    /** Initialize your data structure here. */
    WordDictionary():dict(unordered_map<int,unordered_set<string>>()),lmax(0),lmin(INT_MAX){

    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        dict[word.length()].insert(word);
        if(word.length()>lmax) lmax=word.length();
        if(word.length()<lmin) lmin=word.length();
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        int l=word.length();
        if(l>lmax||l<lmin) return false;
        if(dict[l].count(word)>0) return true;
        int j;
        for(auto i:dict[l])
        {
            if(i.length()!=l)
                continue;
            for(j=0;j<l;j++)
            {
                if(word[j]!='.'&&word[j]!=i[j])
                    break;
            }
            if(j>=l)
                return true;
        }
        return false;
    }
    

    private:
    unordered_map<int,unordered_set<string>> dict;
    int lmax;
    int lmin;
    };


  • 0
    M

    Implementation hiding - hide the TrieNode struct and member function implementations so that definitions can be changed in the future. Don't forget the destructors.

    class WordDictionary {
    public:
        /** Initialize your data structure here. */
        WordDictionary(): root(new TrieNode()) {}
        
        ~WordDictionary() {delete root;}
        
        /** Adds a word into the data structure. */
        void addWord(string word) {
            addWord(word,0,root);
        }
        
        /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
        bool search(string word) {
            return search(word,0,root);
        }
    private:
        struct TrieNode {
            TrieNode():child(vector<TrieNode*>(26,NULL)), isLeaf(false) {}
            ~TrieNode() {for(TrieNode* node:child) delete node;}
            vector<TrieNode*> child;
            bool isLeaf;
        };
        
        TrieNode* root;
        
        void addWord(const string& word, size_t i, TrieNode* cur) {
            if(i==word.length()) return;
            size_t j = word[i] - 'a';
            if(!cur->child[j]) cur->child[j] = new TrieNode();
            if(i==word.length()-1) cur->child[j]->isLeaf=true;
            addWord(word,i+1,cur->child[j]);
        }
        
        bool search(const string& word, size_t i, TrieNode* cur) const {
            if(i==word.length()) return false;
            
            if(word[i]!='.') {
                size_t j = word[i] - 'a';
                if(!cur->child[j]) return false;
                if(i==word.length()-1 && cur->child[j]->isLeaf) return true;
                return search(word,i+1,cur->child[j]);
            }
            else {
                for(TrieNode* node:cur->child) {
                    if(node) {
                        if(i==word.length()-1 && node->isLeaf) return true;
                        if(search(word,i+1,node)) return true;
                    }
                }
                return false;
            }
        }
        
    };
    

  • 0
    S
    This post is deleted!

  • 0
    I

    Does it matter if we don't release the heap memory allocated by new in the interview?


Log in to reply
 

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