Why Memory Limit Exceed


  • 0
    A

    Memory Limit Exceed. But no test case is shown.

    class TrieNode {
        int cnt;
        TrieNode* children[26];
    public:
        // Initialize your data structure here.
        TrieNode() {
            cnt = 0;
            for (int i = 0; i < 26; i++) {
                children[i] = NULL;
            }
        }
        
        ~TrieNode() {
            for (int i = 0; i < 26; i++) {
                if (children[i])
                    delete children[i];
            }
        }
        
        void insert(string& s, int i) {
            if (i == s.length()) cnt++;
            else {
                TrieNode* node = children[s[i]-'a'];
                if (node == NULL) {
                    node = new TrieNode();
                }
                node->insert(s, i+1);
            }
        }  
        
        bool search(string& key, int i) {
            if (i == key.length()) {
                if (cnt) return true;
                else return false;
            }
            else {
                TrieNode* node = children[key[i]-'a'];
                if (node != NULL) {
                    return node->search(key, i+1);
                }
            }
            return false;
        }    
        
        bool startsWith(string& prefix, int i) {
            if (i == prefix.length()) return true;
            else {
                TrieNode* node = children[prefix[i]-'a'];
                if (node != NULL) {
                    return node->startsWith(prefix, i+1);
                }
            }
            return false;
        }
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string s) {
            root->insert(s, 0);
        }
    
        // Returns if the word is in the trie.
        bool search(string key) {
            return root->search(key, 0);
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            return root->startsWith(prefix, 0);
        }
    
    private:
        TrieNode* root;
    };
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie;
    // trie.insert("somestring");
    // trie.search("key");

  • 0
    J

    maybe the recursion have too much deepth?


  • 0
    P
        TrieNode* node = children[s[i]-'a'];
        if (node == NULL) {
            node = new TrieNode();
        }
        node->insert(s, i+1);
    

    You never update children[s[i]-'a'] with the newly allocated node object.


  • 0
    A

    Still do not understand. Could you explain it further? Thanks.


Log in to reply
 

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