C++ Pass Using Trie


  • 2
    1

    Re: C++ Solutions

    A lot of details need to be took care for passing this problem using Trie.

    1. Allocate memory on stack instead of heap. (Though I can not explain why heap memory causes MLE)
    2. Remember to collect/release memory. Because LeetCode Judge might using your function in a way like "class static method". The judge will call it several times, which means managing your in-class memory is extremely important.
    3. Run DFS with memory(can be done using DP) and check for early stop.
    4. Finally, using some tricks for passing it, e.g. skipping long(>100) words, tune parameter for preallocate stack node pool(with size > 27000 is fine for this question).

    Bellow is my passed code, which runs around 650ms.

    struct Node;
    using pNode = Node *;
    //allocate node on stack instead of heap
    pNode pool[27000][26]; // pool size is just tuned by hand to avoid MLE for this question only
    struct Node{
        int idx;
        bool end = false;
        Node(int identity):idx(identity){
            memset(pool[idx], 0, sizeof(pool[idx]));  // remember to reset to NULL because the pool might be polluted by the last run
        }    
    };
    class Solution {
    public:
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            identity = 0; // must reset to 0 because LeetCode judge might use this method as "class static", which is called multi times
            root = new Node(identity++);
            for(auto& w : words)
                if(w.size() < 100) // use a trick here, just skip longer words (specially for this question)
                    insert(root, w, 0);
            vector<string> rtn;
            for(auto& w : words){
                f.assign(w.size()+1, 0);  // dp part, f[i] stands for the max number of words in dict that can be combined into w[i:]
                visit.assign(w.size()+1, false); 
                for(int j = (int)w.size()-1; j>=0; j--)
                    count(w, j); // calculate reversely to avoid too deep recursion
                if(count(w, 0) > 1)
                    rtn.push_back(w);
            }
            collect(root); //must remember to collect history-node, other wise still MLE
            return rtn;
        }
    private:
        Node * root;
        int identity = 0;
        vector<int> f;
        vector<bool> visit;
        void collect(Node* ref){
            if(ref){
                for(int i = 0; i < 26; i++)
                    collect(pool[ref->idx][i]);
                delete ref;
            }
        }
        void insert(Node* ref, string& s, int i){
            if(i == s.size()){
                ref->end = true;
                return;
            }
            if(pool[ref->idx][s[i]-'a'] == NULL)
                pool[ref->idx][s[i]-'a'] = new Node(identity++);
            ref = pool[ref->idx][s[i]-'a'];   
            insert(ref, s, i+1);    
        }
        int count(string&s, int i){
            if(i == s.size())
                return 0;
            if(visit[i])
                return f[i];
            Node* p = root;
            for(int j = i; j < s.size(); j++){
                if(p && pool[p->idx][s[j]-'a'])
                    p = pool[p->idx][s[j]-'a'];
                else
                    break;
                if(p->end){
                    int l = count(s, j+1);
                    f[i] = max(f[i], (l == 0 && j+1 < s.size())? 0 : l+1);
                }
                if((i==0 && f[i] > 1) || (i && f[i])) // early stop to avoid TLE
                    break;
            }
            visit[i] = true;
            return f[i];
        }
    };
    

Log in to reply
 

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