2014
11-19

# 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"].

// LeetCode, Word Break II
// 动规，时间复杂度O(n^2)，空间复杂度O(n^2)
class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string> &dict) {
// 长度为n的字符串有n+1个隔板
vector<bool> f(s.length() + 1, false);
// prev[i][j]为true，表示s[j, i)是一个合法单词，可以从j处切开
// 第一行未用
vector<vector<bool> > prev(s.length() + 1, vector<bool>(s.length()));
f[0] = true;
for (size_t i = 1; i <= s.length(); ++i) {
for (int j = i - 1; j >= 0; --j) {
if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
f[i] = true;
prev[i][j] = true;
}
}
}
vector<string> result;
vector<string> path;
gen_path(s, prev, s.length(), path, result);
return result;

}
private:
// DFS遍历树，生成路径
void gen_path(const string &s, const vector<vector<bool> > &prev,
int cur, vector<string> &path, vector<string> &result) {
if (cur == 0) {
string tmp;
for (auto iter = path.crbegin(); iter != path.crend(); ++iter)
tmp += *iter + " ";
tmp.erase(tmp.end() - 1);
result.push_back(tmp);
}
for (size_t i = 0; i < s.size(); ++i) {
if (prev[cur][i]) {
path.push_back(s.substr(i, cur - i));
gen_path(s, prev, i, path, result);
path.pop_back();
}
}
}
};


Java代码:

public class Solution {
public static List<String> wordBreak(String s, Set<String> dict) {
List<String> dp[] = new ArrayList[s.length()+1];
dp[0] = new ArrayList<String>();
for(int i=0; i<s.length(); i++){
//i是开始位置
if( dp[i] == null ) continue; //前面的部分必须是可以匹配的
for(String word:dict){
int len = word.length();
int end = i+len;
if(end > s.length()) continue;

if(s.substring(i,end).equals(word)){
if(dp[end] == null){
dp[end] = new ArrayList<String>();
}
}
}
}

if(dp[s.length()] == null) return ans;
ArrayList<String> tmp = new ArrayList<String>();
dfsStringList(dp,s.length(),ans, tmp);
return ans;
}

public static void dfsStringList(List<String> dp[],int end,List<String> res, ArrayList<String> tmp){
if(end <= 0){
String ans = tmp.get(tmp.size()-1);
for(int i=tmp.size()-2; i>=0; i--)
ans += (" " + tmp.get(i) );
return;
}
for(String str:dp[end]){
dfsStringList(dp,end-str.length(), res, tmp);
tmp.remove(tmp.size()-1);
}

}
}