Memory limit exceed (iterative version + destructor + 26 children


  • 0
    G
    class TrieNode {
    public:
    
        bool isLeaf;
        TrieNode* child[26];
        // Initialize your data structure here.
        TrieNode() {
          isLeaf = false;
          for(int i=0; i<26; i++)
             child[i] = NULL;
        }
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
            root->isLeaf = true;
        }
    
       ~Trie() {
          destroy(root);
        }
        
        void destroy(TrieNode *r)
        {
            
           for(int i=0; i<26; i++)
           {
               if(r->child[i])
                 destroy(r->child[i]);
           }
           delete r;    
        }
        
        // Inserts a word into the trie.
        void insert(string s) {
            TrieNode *curr = root;
            
            for(int i=0; i<s.size(); i++)
            {
                TrieNode *c = curr->child[s[i]-'a'];
                if(c == NULL)
                {
                    c = new TrieNode();
                }
                curr = c;
            }
            curr->isLeaf = true;
        }
    
        // Returns if the word is in the trie.
        bool search(string key) {
            string s = key;
            TrieNode *curr = root;
            
            for(int i=0; i<s.size(); i++)
            {
                TrieNode *c = curr->child[s[i]-'a'];
                if(c == NULL)
                {
                  return false;
                }
                curr = c;
            }
            return (curr->isLeaf==true);
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            string s = prefix;
            TrieNode *curr = root;
            
            for(int i=0; i<s.size(); i++)
            {
                TrieNode *c = curr->child[s[i]-'a'];
                if(c == NULL)
                {
                  return false;
                }
                curr = c;
            }       
            return true;
        }
    
    private:
        TrieNode* root;
    };
    

    // Your Trie object will be instantiated and called as such:
    // Trie trie;
    // trie.insert("somestring");
    // trie.search("key");


  • 1
    H

    You should change the code in the function of Trie::insert.When c==NULL,it should be curr->child[s[i]-'a']=new TrieNode() but not c=new TrieNode();


  • 0
    G

    Yes...thanks....I looked into it many times but not able to find it.


Log in to reply
 

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