Trie + DFS method using static trie node to avoid getting MLE, runtime about 300ms


  • 0
    T

    If you get MLE, you can try to assign memory from static memory area instead of heap. Below is my AC solution.

    class Solution {
        struct trie_s {
    	    int e;
    	    trie_s* next[26];
    	    trie_s(int _e = 0) : e(_e) {
    		    for(int i = 0; i < 26; i++) next[i] = NULL;
    	    }
        };
    
        bool dfs(trie_s* root, trie_s* t, string& s, int i, int count) {
    	    if(i == s.length()) return count >= 2;
    	    for(int j = i; j < s.length(); j++) {
    		    int x = s[j] - 'a';
    		    if(!t->next[x]) return false;
    		    t = t->next[x];
    		    if(t->e) {
    			    if(dfs(root, root, s, j + 1, count + 1)) return true;
    		    }
        	    }
    	    return false;
        }
    public:
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
    	    vector<string> res;
    	    static trie_s trie_pool[60000], *tr = trie_pool;
    	    memset(trie_pool, 0, sizeof(trie_pool));
    	    int cnt = 1;
    
    	    for(string& s : words) {
    		    trie_s* t = tr;
    		    for(int i = 0; i < s.length(); i++) {
    			    int x = s[i] - 'a';
    			    if(!t->next[x]) t->next[x] = &trie_pool[cnt++];
    			    if(i == s.length() - 1) t->next[x]->e = 1;
    			    t = t->next[x];
    		    }
    	    }
    	    for(string& s : words) {
    		    if(dfs(tr, tr, s, 0, 0)) res.push_back(s);
     	    }
    
    	    return res;
        }
    };

Log in to reply
 

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