[recommend for beginners]clean DP C++ implementation with detailed explanation

• Define substring[i, j] is the sub string from i to j.

``````  (substring[i,j] == word) :   result[i] = substring[i,j] + {result[j]}
``````

So, it's better to evaluate it backword.

For example:

``````   s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
``````

THE PROCESS:

`````` 0  c  "cat"  -- word[0,2] + {result[3]}  ==> "cat sand dog"
"cats" -- word[0,3] + {result[4]}  ==> "cats and dog"
1  a  ""
2  t  ""
3  s  "sand" --  word[3,6] + {result[7]} ==> "sand dog"
4  a  "and"  --  word[4,6] + {result[7]} ==> "and dog"
5  n  ""
6  d  ""
7  d  "dog"
8  o  ""
9  g  ""
``````

In fact, you should know that the actual process is reverse the above example.

``````class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
/*** result[i] : record the valid word break result of s[i, end] **/
vector<vector<string>> result(s.size());
for(int i=s.size()-1; i>=0; i--){
vector<string> v;
result[i]=v;
for(int j=i+1; j<=s.size(); j++){
string word=s.substr(i, j-i);
if(wordDict.find(word)!=wordDict.end()){
if(j==s.size()){
result[i].push_back(word);
}
else{
for(int k=0; k<result[j].size(); k++){
result[i].push_back(word+" "+result[j][k]);
}
}
}
}
}
return result[0];
}
};
``````

• "aaaaaaaaaaaaaaaaaaaaaaaaaaaa.....aaaaaaabaaaaaaaaaaaaaaaaaa.......aaaaaaaaaaaaaaaaaaaaaaaaa"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

can not be passed

It will cause the memory limit exceeded MLE

• So why did it get a MLE? Is it because that you store all `result[i]`?

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