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

• 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

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