C++: From 556 ms DP to 342 ms Backtracking


  • 0
    W

    My initial solution is to use trie. But as reported by other friends, I also suffered from MLE error. This problem was solved in C++ Pass Using Trie, which allocates TrieNode memory on stack instead of heap. (Any one knows the underlying story??)

    Then I tried my DP solution. The idea is: first see if a substring of s (s[0, ..., i]) matches another word, or it is a concatenation of multiple words. If yes, we continue to find if s[i, ..., j] is another words from dict. If the answer is still yes, we would know that s[0, ..., j] is a concatenation of multiple words. A variable dp is used to record the status, where dp[i] = 1 indicates s[0, ... ,i] is a concatenation of N words, where N>=1. String s will be inserted to the final result if s[s.length()-1] == 1. Pay attention to that in the first step, variable i can't be set to s.length() - 1. If doing this, the substring would be the whole string itself, and can be found in the dict. Hence every words would be included into the result.

        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            unordered_set<string> wordSet(words.begin(), words.end());
            vector<string> res;
            for(auto s : words) {
                int len = s.length();
                vector<int> dp(len, 0); // dp[i] = 1: s[0,..,i] is in the dict
                for(int i = 0; i < len - 1; i ++) { // Note that i can't be len - 1, otherwise, the substr is itself
                    if(dp[i] == 0 && wordSet.count(s.substr(0, i + 1)) == 0) { // s[0,...,i] isn't in dict
                        continue;
                    }
                    dp[i] = 1;
                    
                    for(int j = i + 1; j < len; j ++) { // judge if s[i+1, j] can be found in the dict
                        if(wordSet.count(s.substr(i+1, j-i)))
                            dp[j] = 1;
                    }
                    if(dp.back()) {
                        res.push_back(s);
                        break;
                    }
                }
            }
            return res;
        }
    

    A similar idea using backtracking is attached, which reduces the runtime from 556 ms to 342 ms.

        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            vector<string> res;
            if(words.size() < 2)
                return res;
            unordered_set<string> wordSet(words.begin(), words.end());
            for(auto s : words) {
                if(helper(s, 0, wordSet)) {
                    res.push_back(s);
                }
            }
            return res;
        }
        
        bool helper(string& s, int pos, unordered_set<string>& wordSet) {
            if(pos >= s.length())
                return true;
            int i_max = s.length() - 1 - (pos==0?1:0);
            for(int i = i_max; i >= pos; i --) {
                if(wordSet.count(s.substr(pos, i - pos + 1))) {
                    if(helper(s, i + 1, wordSet))
                        return true;
                }
            }
            return false;
        }
    

Log in to reply
 

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