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..


  • 5
    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.


Log in to reply
 

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