C++, trie solution, but memory limited, who can point me what is wrong here?


  • 0
    J
    class TriNode
    {
    public:
        vector<TriNode*> children;
        bool isEnd;
        TriNode()
        {
            children = vector<TriNode*>(26,NULL);
            isEnd = false;
        }
    };
    class TriTree
    {
    public:
        TriTree()
        {
            root = new TriNode();
        }
        void addWord(string word)
        {
          TriNode *curr = root;
          for(int i =  0;i<word.size();i++)
          {
              if(curr->children[word[i]-'a']==NULL)
                  curr->children[word[i]-'a'] = new TriNode();
              curr = curr->children[word[i]-'a'];
          }
          curr->isEnd = true;
        }
        
        string searchWord(string word)
        {
           TriNode*curr = root;
           string res;
           for(int i = 0;i<word.size();i++)
           {
               res = res + word[i];
               if(curr->children[word[i]-'a']!=NULL)
               {   
            
                    curr = curr->children[word[i]-'a'];
                    if(curr->isEnd==true)
                        return res;
               }   
               else 
                   return word;
           }
           return word;
        }
    
    private:
        TriNode *root;
    };
    
    
    class Solution {
    public:
        string replaceWords(vector<string>& dict, string sentence) {
            string result;
            TriTree tri_tree;
            for(int i = 0;i<dict.size();i++) 
                tri_tree.addWord(dict[i]);
            string token;
            stringstream ss(sentence); // Insert the string into a stream
            while(ss>>token)
            {
                string replace = tri_tree.searchWord(token);
                result  = result + replace;
                result+=" ";
            }
            return result.substr(0,result.size()-1);    
        }
    };
    

Log in to reply
 

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