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"].
题目大意就是：给一个string，一个词典，把这个string根据词典构建出所有可能的组合。
我的解法就是预处理+DFS+剪枝。
1、首先用一个breakFlag数组，记录string中的各个位置为结尾是否是合法的分词末尾，以上面的样例来说，c,a都是不合法的分词结尾，t,s都是合法的分词结尾。
2、然后用DFS来搜全部可能的组合，如果最后正好分完这个string，说明是合法的分词方法，组合成句子然后添加到结果List中，有个小优化就是可以先把字典里的单词的长度放入一个array，分词的时候只需要遍历这个array就可以，比如上面的字典里单词长度只有{3,4}组成一个array，只需要遍历cat cats就可以继续往后遍历了。
Talk is cheap>>
package leetcode; import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set; public class WordBreakII { public static void main(String[] args) {
Set<String> set = new HashSet<String>();
set.add("cat");
set.add("cats");
set.add("and");
set.add("sand");
set.add("dog");
new WordBreakII().wordBreak("catsanddog", set);
} Set<Integer> lenArray = new HashSet<>();
boolean[] breakFlag; public List<String> wordBreak(String s, Set<String> dict) {
List<String> res = new ArrayList<>();
for (String next : dict) {
lenArray.add(next.length());
}
breakFlag = new boolean[s.length() + 1];
breakFlag[0] = true;
for (int i = 0; i < s.length(); i++) {
if (breakFlag[i]) {
for (int j = 0; i + j < s.length() + 1; j++) {
if (dict.contains(s.substring(i, i + j)))
breakFlag[i + j] = true;
}
}
}
if (breakFlag[s.length()])
dfs(s, "", dict, res, s.length());
return res;
} public void dfs(String src, String tmp, Set<String> dict, List<String> res, int length) {
if (length < 0) {
return;
}
if (length == 0) {
System.out.println(tmp.substring(0, tmp.length() - 1));
res.add(tmp.substring(0, tmp.length() - 1));
return;
}
for (int len : lenArray) {
int left = src.length() - len;
if (left < 0)
break;
String t = src.substring(left, src.length());
if (breakFlag[length] && dict.contains(t)) {
dfs(src.substring(0, left), t + " " + tmp, dict, res, length - len);
}
}
} }