Why my C++ code using trie is getting MLE?


  • 0
    M
    class Solution {
    public:
        struct TrieNode{
            bool isWord = false;
            TrieNode* next[26];
        };
        
        TrieNode* root = new TrieNode();
        
        void addTrie(string& word) {
            TrieNode* cur = root;
            for (char c:word) {
                if (cur->next[c-'a'] == NULL) {
                    cur->next[c-'a'] = new TrieNode();
                }
                cur = cur->next[c-'a'];
            }
            cur->isWord = true;
        }
        
        string findWord(string word) {
            TrieNode* cur = root;
            for (int i = 0; i < word.size(); i++) {
                if (cur->isWord) {
                    return word.substr(0,i);
                }
                if (cur->next[word[i]-'a']) {
                    cur = cur->next[word[i]-'a'];
                }
                else {
                    return word;
                }
            }
            return word;
        }
        
        string replaceWords(vector<string>& dict, string sentence) {
            for (string& w:dict) {
                addTrie(w);
            }
            istringstream iss(sentence);
            string word, res;
            while (iss >> word) {
                word = findWord(word);
                res = res + word + " ";
            }
            return res.substr(0, res.size()-1);
        }
    };
    

Log in to reply
 

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