# [leetcode] Word Break II

### Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

First, I used a similar algorithm as the one I used in problem Word Break I. However, I met Time Limit Exceeded error. The time complexity is o(n!). I realized I need to use more space to compensate the cost in time.

T(n) = \sum^n-1_(i = 1)(T(i)*T(n – 1))

Instead of storing path in dynamic programming array, I stored the last jump position in it. Finally, backtracking algorithm is used to retrieve the available path.

Postorder DFS+DP

class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
if(s.size() == 0 || wordDict.empty() == true) return vector<string>();
vector<int> dp[s.size()]; //store the last step of dp[i]
for(int i = 0; i < s.size(); i++){
for(int j = i; j >= 0; j--){
string str = s.substr(j, i - j + 1);
if(wordDict.find(str) != wordDict.end()){
//str exists in dict
if(j == 0 || dp[j - 1].empty() == false){ // this line is important, dynamic programming should use previous elements in array.
dp[i].push_back(j);
}
}
}
}
string path;
vector<string> paths;
//retrieve the path
retrievePath(s, dp, s.size() - 1, path, paths);
return paths;
}
//backtracking
void retrievePath(string s, vector<int> dp[], int pos, string path, vector<string>& paths){
//base condition
if(pos == -1){
paths.push_back(path);
}
//backtracking
else if(dp[pos].empty()){
return ;
}
else{
//ordinary condition
if(pos != s.size() - 1){
//not the first step, path is not empty
path.insert(0, " ");
}
for(auto it = dp[pos].begin();  it != dp[pos].end(); it++){
string newPath = path;
newPath.insert(0, s.substr(*it, pos - *it + 1));
retrievePath(s, dp, *it - 1, newPath, paths);
}
}
}
};

Preorder DFS+DP

class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
if(s.size() == 0) return vector<string>();
auto dp = vector<vector<int>>(s.size(), vector<int>());
for(int i = 0; i < s.size(); i++){
if(wordDict.count(s.substr(0, i+1)) > 0){
dp[i].push_back(0);
}
}
for(int i = 0; i < s.size() - 1; i++){
if(!dp[i].empty()){
for(int j = i+1; j < s.size(); j++){
if(wordDict.count(s.substr(i+1, j - i)) > 0){
dp[j].push_back(i+1);
}
}
}
}
return DFS(s, dp, s.size() - 1);
}
vector<string> DFS(string& s, vector<vector<int>>& dp, int pos){
// base condition
vector<string> ans;
if(pos < 0){
ans.push_back("");
return ans;
}
for(auto it = dp[pos].begin(); it!= dp[pos].end(); it++){
auto thisAns = DFS(s, dp, *it - 1);
for(auto itthisAns = thisAns.begin(); itthisAns != thisAns.end(); itthisAns++){
if(!(*itthisAns).empty()) (*itthisAns).push_back(' ');
(*itthisAns).append(s.substr(*it, pos - *it + 1));
ans.push_back(*itthisAns);
}
}
return ans;
}
};

This site uses Akismet to reduce spam. Learn how your comment data is processed.