memory limited exceed


  • 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;
    }

    int searchWord(string word)
    {
       TriNode*curr = root;
       for(int i = 0;i<word.size();i++)
       {
           if(curr->children[word[i]-'a']!=NULL)
           {
         
               curr = curr->children[word[i]-'a'];
               if(curr->isEnd==true) //check whether the end of the word, should be after the above line.
                   return i+1;
           }   
           else 
               return -1;
       }
       return -1;
    }
    

    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)
    {
    int idx = tri_tree.searchWord(token);
    if(idx == -1) result = result + token;
    else result = result+token.substr(0,idx);
    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.