[recommend for beginners]clean C++ implementation with detailed explanation


  • 2
    class TrieNode {
    public:
        // Initialize your data structure here.
        TrieNode():isWord(false) {}
        unordered_map<char, TrieNode*> children;
        bool isWord;
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string word) {
            if(word.size()<=0)  return;
            TrieNode* node=root;
            for(int i=0; i<word.size(); i++){
                if(node->children.find(word[i])==node->children.end()){
                    node->children[word[i]]=new TrieNode();
                }
                node=node->children[word[i]];
            }
            node->isWord=true;
        }
    
        // Returns if the word is in the trie.
        bool search(string word) {
            return retrieve(word, true);
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            return retrieve(prefix, false);
        }
    
    private:
        inline bool retrieve(const string& key, bool isWord){
            if(key.size()<=0)  return false;
            TrieNode *node=root;
            for(int i=0; i<key.size(); i++){
                if(node->children.find(key[i])==node->children.end())
                    return false;
                node=node->children[key[i]];
            }
            return isWord ? node->isWord : true;
        }
        
        TrieNode* root;
    };
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie;
    // trie.insert("somestring");
    // trie.search("key");

  • 0
    2

    I made 2 mistaks

    first

         -1-  TrieNode structure should include isWord and unorder_map<char, ...> 
    
           class TrieNode {
           public:
                // Initialize your data structure here.
               bool isWord;
               unordered_map<char, TrieNode*> children;
               TrieNode() : isWord(false) {
            
                }
            };
    

    second is

         cur->children[word[i]] = new TrieNode();
    
          but not   
    
         cur->children[word[i]] = new TrieNode(word[i]);

Log in to reply
 

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