575，回溯算法和DFS解单词拆分 II
You reap what you sow.
一分耕耘，一分收获。
问题描述
来源：LeetCode第140题
难度：困难
给定一个非空字符串s和一个包含非空单词列表的字典wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
"cats and dog",
"cat sand dog"
]
示例 2：
输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。
示例 3：
输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]
回溯算法解决
前面我们分别通过动态规划，DFS以及BFS三种方式来判断字符串是否可以拆分，具体可以看下
今天这题不光要判断字符串是否可以拆分，如果可以拆分还要打印所有可能的拆分结果。判断是否可拆分比较简单，我们直接使用第573题动态规划的方式来判断即可，如果不能拆分我们直接返回一个空的集合，如果可以拆分我们就拆分。
拆分的原理比较简单，我们逐渐截取子串，判断是否在字典中，如果不在字典中就继续截取更长的子串……，如果在字典中我们就沿着这个路径走下，如下图所示（这里是有两组结果，由于图画不下了，剩下的使用省略号没有画出来），我们可以把它看做是一棵n叉树
对于n叉树的路径我们可以使用回溯算法来解决，回溯算法我们之前也讲过很多次了，具体可以看下450，什么叫回溯算法，一看就会，一写就废，其实他有一个经典的模板
1private void backtrack("原始参数") {
2 //终止条件(递归必须要有终止条件)
3 if ("终止条件") {
4 //一些逻辑操作（可有可无，视情况而定）
5 return;
6 }
7
8 for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
9 //一些逻辑操作（可有可无，视情况而定）
10
11 //做出选择
12
13 //递归
14 backtrack("新的参数");
15 //一些逻辑操作（可有可无，视情况而定）
16
17 //撤销选择
18 }
19}
我们对这个模板稍微修改一下就是今天这题的答案，虽然这是一道hard题，但经过我们的逐步分析，发现也不是那么难，来看下代码
1public List<String> wordBreak(String s, List<String> wordDict) {
2 //集合Set的查找效率要比集合list高，这里为了提高效率，
3 //先把list转化为集合set
4 Set<String> set = new HashSet<>(wordDict);
5 //下面是动态规划方式，判断字符串被拆解的子串是否都在字典中
6 int length = s.length();
7 boolean[] dp = new boolean[length + 1];
8 dp[0] = true;//边界条件
9 for (int i = 1; i <= length; i++) {
10 for (int j = 0; j < i; j++) {
11 dp[i] = dp[j] && set.contains(s.substring(j, i));
12 if (dp[i]) {
13 break;
14 }
15 }
16 }
17 List<String> res = new ArrayList<>();
18 //如果不能拆解，直接返回空的集合就行了
19 if (!dp[length])
20 return res;
21 //如果能被拆解，我们通过回溯方式执行拆解
22 traceback(s, set, 0, res, new ArrayList<>());
23 return res;
24}
25
26//回溯方式拆解字符串
27private void traceback(String s, Set<String> wordDict, int start, List<String> res, List<String> path) {
28 if (start == s.length()) {
29 //下面这两行代码都是字符串加空格然后拼接，一个是官方提供的方法，
30 //一个是我自己写的，都可以实现
31 //res.add(String.join(" ", path));
32 res.add(join(path));
33 return;
34 }
35 for (int i = start + 1; i <= s.length(); i++) {
36 //拆解字符串
37 String str = s.substring(start, i);
38 //如果拆解的子串不存在于字典中，就继续扩大子串
39 if (!wordDict.contains(str))
40 continue;
41 //如果拆解的子串存在于字典中，就把子串添加到path中
42 path.add(str);
43 //往下继续递归
44 traceback(s, wordDict, i, res, path);
45 //执行回溯，把之前添加的子串给移除
46 path.remove(path.size() - 1);
47 }
48}
49
50//字符串加空格拼接
51private String join(List<String> path) {
52 StringBuilder stringBuilder = new StringBuilder();
53 for (int i = 0; i < path.size(); i++) {
54 stringBuilder.append(path.get(i));
55 if (i != path.size() - 1)
56 stringBuilder.append(" ");
57 }
58 return stringBuilder.toString();
59}
DFS解决
回溯算法比较容易理解，这题我们还可以使用DFS来解决。比如我们进行截取的时候，如果截取的子串存在于字典中，我们通过递归的方式拆分剩下的，如果剩下的能够拆分我们就把当前拆分的子串和剩下拆分的结果进行拼接，如果剩下的不能拆分，不会进行任何拼接，直接返回空的集合即可，其实这种思路还可以借鉴《464. BFS和DFS解二叉树的所有路径》的最后一种解法，实现原理如下所示
来看下代码
1public List<String> wordBreak(String s, List<String> wordDict) {
2 return backtrack(s, new HashSet<>(wordDict), 0);
3}
4
5public List<String> backtrack(String s, Set<String> wordDict, int start) {
6 List<String> res = new ArrayList<>();
7 for (int i = start + 1; i <= s.length(); i++) {
8 String str = s.substring(start, i);
9 //如果拆解的子串不存在于字典中，就继续拆
10 if (!wordDict.contains(str))
11 continue;
12 //走到下面这个地方，说明拆分的子串str存在于字典中
13 //如果正好拆完了，我们直接把最后一个子串添加到res中返回
14 if (i == s.length())
15 res.add(str);
16 else {
17 //如果没有拆完，我们对剩下的子串继续拆分
18 List<String> remainRes = backtrack(s, wordDict, i);
19 //然后用当前的子串str和剩下的子串进行拼接（注意如果剩下的子串不能
20 //完全拆分，remainRes就会为空，就不会进行拼接）
21 for (String remainStr : remainRes) {
22 res.add(str + " " + remainStr);
23 }
24 }
25 }
26 return res;
27}
我们知道递归必须要有终止条件的，但这题好像没有，其实是有的，当for循环不满足条件的时候，就不会再调用自己了。
截止到目前我已经写了500多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有1000多页，大家可以在公众号中回复关键字“pdf”即可获取下载链接。