C++ Solutions, Backtrack, DP, or Trie.


  • 4
    W

    First, I provide my working solution using unorederd_set. But I think a better solution should use Trie. Though it passed all test cases, I always get MLE. But the java solution using Trie can be accepted. Did anybody have any suggestions about this? I have already made some optimization on it, e.g., a word that can be concatenated by shorter words will not be inserted into the Trie. But I still get MLE.

    unordered_set solution 486 ms

    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            vector<string> result;
            if(words.empty()) return result; 
            auto mycomp = [&](const string& str1, const string& str2){return str1.size() < str2.size();};
            sort(words.begin(), words.end(), mycomp);
            unordered_set<string> mp;
            for(auto& word: words) {
                string path = "";
                if(dfs(word, 0, path, 0, mp)) result.push_back(word); // We don't need to insert this word, because it can be concatenated from other words.
                else mp.insert(word); 
            }
            return result;
        }
        
    private:
        bool dfs(string& word, int pos, string& path, int nb, unordered_set<string>& mp) {
            if(pos == word.size()) {
                if(mp.find(path) != mp.end() && nb > 0) return true;
                else return false;
            }
            path.push_back(word[pos]);
            if(mp.find(path) != mp.end()) {
                string temp = "";
                if(dfs(word, pos+1, temp, nb+1, mp)) return true;
            }
            if(dfs(word, pos+1, path, nb, mp)) return true;
            else return false;
        }
    

    DP solution based on Word Break 739 ms

    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            vector<string> result;
            if(words.empty()) return result; 
            auto mycomp = [&](const string& str1, const string& str2){return str1.size() < str2.size();};
            sort(words.begin(), words.end(), mycomp);
            unordered_set<string> mp;
            for(auto& word: words) {
                string path = "";
                if(wordBreak(word, mp)) result.push_back(word); // We don't need to insert this word, because it can be concatenated from other words.
                else mp.insert(word); 
            }
            return result;
        }
        
    private:
        bool wordBreak(string& s, unordered_set<string>& wordDict) {
            if(s.empty() || wordDict.empty()) return false;
            vector<bool> dp(s.size()+1, false);
            dp[0] = true;
            for(int i = 1; i <= s.size(); i++) {
                for(int k = i-1; k >= 0; k--) {
                    if(dp[k] && wordDict.find(s.substr(k, i-k)) != wordDict.end()) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.size()];
        }
    

    Here I provide my Trie-based solution, but it gets MLE.

    class Solution {
    public:
        struct TrieNode {
            bool isWord;
            unordered_map<char, TrieNode*> children;
            TrieNode(): isWord(false) {};
        };
    
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            vector<string> result;
            if(words.empty()) return result; 
            auto mycomp = [&](const string& str1, const string& str2){return str1.size() < str2.size();};
            sort(words.begin(), words.end(), mycomp);
            
            root = new TrieNode();
            for(auto& word: words) {
                if(dfs(word, 0, root, 0)) result.push_back(word);
                else insert(word);
            }
            return result;
        }
        
    private:
        TrieNode* root;
        
        void insert(string& word) {
            auto run = root;
            for(char c: word) {
                if(run->children.find(c) == run->children.end()) {
                    TrieNode* newnode = new TrieNode();
                    run->children[c] = newnode;
                }
                run = run->children[c];
            }
            run->isWord = true;
        }
        
        bool dfs(string& word, int pos, TrieNode* node, int nb) {
            if(pos == word.size()) {
                if(node->isWord && nb > 0) return true;
                else return false;
            }
            
            if(node->children.find(word[pos]) == node->children.end()) return false;
            auto next = node->children[word[pos]];
            if(next->isWord) {
                if(dfs(word, pos+1, root, nb+1)) return true;
            }
            if(dfs(word, pos+1, next, nb)) return true;
            else return false;
        }
    };
    

  • 2
    Y

    I aslo get MLE with Trie..


  • 6
    1

    A lot of details need to be take cared 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];
        }
    };
    

  • 0
    W

    @1069450252-qq-com Hi, thanks for sharing your solution. You are really a master of C++!


  • 0
    L

    I find wangxinbo's original trie-based solution a bit easier to understand. After using 1069450252-qq-com's "pointer pool" to workaround the MLE problem, the code is accepted and also runs pretty fast - three runs with 205 ms (98%), 175 ms (100%), and 215 ms (98%).

    struct TrieNode;
    
    // Allocate node on stack instead of heap. The pool size is
    // just tuned by hand to avoid MLE for this question only.
    TrieNode* pool[54000][26];
    
    struct TrieNode{
        TrieNode(int identity) : idx(identity) {
            // Reset to NULL because the pool might be polluted by the last run.
            memset(pool[idx], 0, sizeof(pool[idx]));
            children = pool[idx];
        }    
        int idx;
        bool isWord = false;
        TrieNode** children = nullptr;
    };
    
    class Trie {
    public:
        Trie() : root(new TrieNode(identity++)) {}
    
        void insert(TrieNode* root, string& word) {
            auto node = root;
            for(char c: word) {
                if(node->children[c - 'a'] == nullptr) {
                    TrieNode* newNode = new TrieNode(identity++);
                    node->children[c - 'a'] = newNode;
                }
                node = node->children[c - 'a'];
            }
            node->isWord = true;
        }
        
    private:
        int identity = 0;
        
    public:
        TrieNode* root = nullptr;
    };
    
    class Solution {
    public:
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            vector<string> result;
            if(words.empty()) return result; 
            auto mycomp = [&](const string& str1, const string& str2){return str1.size() < str2.size();};
            sort(words.begin(), words.end(), mycomp);
            
            Trie trie;
            for(auto& word: words) {
                if(dfs(trie.root, word, 0, trie.root, 0)) result.push_back(word);
                else trie.insert(trie.root, word);
            }
            return result;
        }
        
    private:
        bool dfs(TrieNode* root, string& word, int pos, TrieNode* node, int num_words) {
            if(pos == word.size()) {
                if(node->isWord && num_words > 0) return true;
                else return false;
            }
            
            if(node->children[word[pos] - 'a'] == nullptr) return false;
            auto next = node->children[word[pos] - 'a'];
            if(next->isWord) {
                if(dfs(root, word, pos + 1, root, num_words + 1)) return true;
            }
            if(dfs(root, word, pos + 1, next, num_words)) return true;
            else return false;
        }
    };
    
    

  • 0

    For the dp solution:
    I used k to loop from 0 to i - 1, but got TLE.
    I believe this is because to let k loops from i - 1 to 0 makes it more likely that
    smaller string

    s.substr(k, i - k)

    exists in the hashtable.


  • 0
    A

    @1069450252-qq-com I think the OJ has a limited amount of the heap memory. The buffer you declared is a global variable (if OJ doesn't wrap it but just append a main function to run and test the program). As global variables are allocated in the data segment and it is fixed during the execution of the program (heap is not). We won't get MLE here as the memory is already allocated in the beginning of the execution.


Log in to reply
 

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