Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.
给定一个非空串S和一个包含非空单词的列表Dict，给串S添加空格构建一个句子使得每一个单词是Dict中的一个单词。其中Dict中无重复单词。
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"].
解析：看完题第一个反应就是深搜，快速生成代码：
void dfs(String s, List<String> ret, List<String> Dict, List<String> buff) {
if (s.length() == 0) {
ret.add(String.join(" ",buff));
return;
}
for (int i = 0; i < Dict.size(); i++) {
if (s.startsWith(Dict.get(i))) {
String t = Dict.get(i);
buff.add(t);
dfs(s.substring(t.length()), ret, Dict, buff);
buff.remove(buff.size() - 1);
}
}
}
public List<String> wordBreak(String s, List<String> wordDict) {
List<String> ret = new ArrayList<>();
List<String> buff = new ArrayList<>();
dfs(s, ret, wordDict, buff);
return ret;
}
结果是TLE，挂在下面Case上：
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
想想很明显，是dfs中的for进行了许多无用的搜索造成的，解决方法无非就是DP或剪枝。看题目标签是DP，修改成DP解法。
void dfs(int [][] dp, List<String> ret, List<String> buff,int step,List<String> Dict) {
if(step == dp.length){
ret.add(String.join(" ", buff));
return;
}
for(int i = 0; i < dp.length; i++){
int strind = dp[i][step];
if(strind > 0){
buff.add(Dict.get(strind - 1));
dfs(dp,ret, buff,step+Dict.get(strind - 1).length(), Dict);
buff.remove(buff.size()-1);
}
}
}
private void show(int [][]dp){
for(int i = 0; i < dp.length; i++){
System.out.println();
for(int j = 0; j < dp.length; j++){
System.out.printf("%3d", dp[i][j]);
}
}
}
public List<String> wordBreak(String s, List<String> wordDict) {
List<String> ret = new ArrayList<>();
//将字典加入到map中
Map<String,Integer> dic = new HashMap<>();
for(int i = 0; i < wordDict.size(); i++){dic.put(wordDict.get(i),i+1);}
int sLen = s.length();
int [][] dp = new int[sLen][sLen];
boolean connected[] = new boolean[sLen];
//填表
for(int i = s.length()-1; i > -1; i--){
int increLen = s.substring(i).length();
for(int j = 0; j < increLen; j++){//System.out.println(s.substring(i, i+j+1));
int ti = i+j+1;
if(dic.containsKey(s.substring(i, ti)) && (i+j+1==sLen || connected[ti])){
connected[i] = true;
dp[j][i]=dic.get( s.substring(i, ti) );
}
}
}
//show(dp);
//dfs遍历结果。
dfs(dp,ret, new ArrayList<String>(),0,wordDict);
return ret;
}