Help! can anyone save my MLE solution?


  • 0
    S
    
    class Solution {
    public:
        struct node{
            map<char, node> m;
            bool flag;
            node() { flag = false;}
            void insert(string &s){
                auto n = this;
                for (auto c: s){
                    auto it = n->m.find(c);
                    if (it == n->m.end())
                        n->m[c] = node();
                    n = &(n->m[c]);
                }
                n->flag = true;
            }
        } root;
        string solve(string w){
            node* n = &root;
            for (int i = 0; i < w.size(); i++){
                auto c = w[i];
                auto it = n->m.find(c);
                if (it == n->m.end()) return w;
                n = &(n->m[c]);
                if (n->flag) return w.substr(0, i + 1);
            }
            return w;
        }
        string replaceWords(vector<string>& dict, string sentence) {
            for (auto &w: dict) root.insert(w);
            int last = -1;
            string ret;
            sentence += ' ';
            for (int i = 0; i < sentence.size(); i++){
                if (sentence[i] == ' '){
                    ret = ret + solve(sentence.substr(last + 1, i - last - 1)) + " ";
                    last = i;
                }
            }
            ret.resize(ret.size() - 1);
            root.m.clear();
            return ret;
        }
    };
    

  • 0
    N

    sizeof(map<char, node>) is 48 in a class object, which can cause MLE if Trie is too big.


Log in to reply
 

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