# [HELP] really have no idea why my DP solution get a TLE. This should have a same result as accpected recursion solution(memorized)

• The idea is to use a DP array vector<vector<string>> to remember word break result at each idx. Traverse from the head of the string to the end. And for each idx, iterate all possible word and add to previous idx result. As the code show:

``````class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
vector<vector<string>> dp(s.size(), vector<string>(0));
int max_s = 0;
for (unordered_set<string>::iterator it = wordDict.begin(); it != wordDict.end(); it++) {
max_s = max(max_s, (int)(*it).size());
}

for (int i = 0; i < s.size(); i++) {
for (int j = i; j >= 0 && i - j + 1 <= max_s; j--) {
string cur_string = s.substr(j, i - j + 1);

if (wordDict.find(cur_string) != wordDict.end()) {
// found a string from idx j to i.
// got from dp[j-1]
if (j == 0) {
dp[i].push_back(cur_string);
} else if (dp[j-1].size() > 0){
for (int k = 0;  k < dp[j-1].size(); k++) {
dp[i].push_back(dp[j-1][k] + " " + cur_string);
}
}
}
}
}

return dp.back();
}
};
``````

Per my understanding, this solution didn't do any redundant work comaparing to recursion. However, this code get TLE consistently. Can anyone take a look and see if I missed anything here?

Thanks!!

• I guess it might be due to two reasons:

• You looped from 1 to the length of the longest word in wordDict. If there is at least one single very very long word in wordDict, and if there are not many words in wordDict, then your algo does lots of unnecessary checks.
• The recursive method fills only the queried parts of the DP table. However, an iterative method usually fills the entire table even if some parts of it is not needed. Example input: `s = "aaaaaaaa", dict = ["aaaa"]`.

The following is my Java approach which fixes the two issues above

``````public class Solution {
private String s;
private Set<String> wordDict;
private Set<Integer> wordSizes;
public List<String> wordBreak(String s, Set<String> wordDict) {
for(int i=0;i<=s.length();i++)
dp.set(0,empty);

wordSizes = new TreeSet<Integer>();
for(String word : wordDict)

this.s = s;
this.wordDict = wordDict;
return getListEndedAt(s.length());
}
if(rtn!=null)
return rtn;
for(int wordSize : wordSizes){
if(i-wordSize<0)
break;    //TreeSet is a sorted set.
String substr = s.substring(i-wordSize,i);
if(!wordDict.contains(substr))
continue;
for(String prev : getListEndedAt(i-wordSize)){
if(i==wordSize)