NEED HELP! Iterative vs Recursive DP, why Iterative got TLE?


  • 0
    N

    Same algorithm in different implementation

    The Recursive:

    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            unordered_map<string, vector<string> > dp;
            return backtrack(s, wordDict,  dp);
        }
        
        vector<string> backtrack(string  s, unordered_set<string>& wordDict,  unordered_map<string, vector<string> > & dp) {
                        if (dp.find(s) != dp.end()) {
                             return dp[s];
                        }
                    
                        vector<string> result;
                        for (int i = 0; i < s.size(); i++) {
                            string temp = s.substr(0, i + 1);
                            if (wordDict.find(temp) != wordDict.end()) {
                                if (i == s.size() - 1) {
                                    result.push_back(temp);
                                       
                                } else {
                                    vector<string> res = backtrack(s.substr(i + 1), wordDict,  dp);
                                    for (auto s : res) {
                                        result.push_back(temp + " " + s);
                                    }
                                }
                            }
                        }
                        dp.insert(pair<string, vector<string> >(s, result));
                        return result;
        }
    

    The Iteration:

    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            unordered_map<string, vector<string> > dp;
            for (int i = 0; i < s.size(); i++) {
                int j = i;
                vector<string> res;
                while (j >= 0) {
                    string curr = s.substr(j, i - j + 1);
                    if (wordDict.find(curr) != wordDict.end()) {
                        if (j == 0) {
                            res.push_back(curr);
                        } else {
                            string prev = s.substr(0, j);
                            for (auto s : dp[prev]) {
                                res.push_back(s + " " + curr);
                            }
                        }
                    }
                    j--;
                }
                dp.insert(pair<string, vector<string> >(s.substr(0, i + 1), res));
            }
            return dp[s];
        }
    

    However, the recursive one got accepted, but iterative got TLE, can someone explain why?
    Thanks


Log in to reply
 

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