why there is a MLE in my c++ trie code ?


  • 0
    Z
    class TrieNode{
    friend class Trie;
        //char content;
        bool isleaf;
        TrieNode* next[26];
        TrieNode():isleaf(false){memset(next,0,sizeof(next));}
        TrieNode(bool flag1):isleaf(flag1){memset(next,0,sizeof(next));}
    };
    class Trie{
    friend class Solution;
        public: 
        Trie(){
            root=new TrieNode();
        }
        
        //~Trie(){}
        void insertWord(string word){
            TrieNode *curr=root;
            for(int x:word){
                if(!curr->next[x-'a']) curr->next[x-'a']=new TrieNode(0);
                curr=curr->next[x-'a'];
              //  cout<<curr->content<<"%"<<curr->isleaf<<endl;
            } 
            curr->isleaf=1;
        }
       bool testWord(string word, int index,  int count) { 
            TrieNode* curr = root;
            int n = word.size();
            for (int i = index; i < n; i++) {
                if (curr->next[word[i] - 'a'] == nullptr) {
                    return false;
                }
                if (curr->next[word[i] - 'a']->isleaf) {
                    if (i == n - 1) { 
                        return count >= 1;
                    }
                    if (testWord(word, i + 1, count + 1)) {
                        return true;
                    }
                }
                curr = curr->next[word[i] - 'a'];
            }
            return false;
        }        
    
    private:
        TrieNode* root;
    };
    class Solution {
    public:
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            
            vector<string> res;
            if(words.empty()) return res;
            Trie dic;
            for(auto x:words)
                dic.insertWord(x);
            for(auto x:words){
                if(dic.testWord(x,0,0))
                    res.push_back(x);
            }
            return res;
        }
    };
    

Log in to reply
 

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