LeetCode 140. 单词拆分 II
目录
题目描述
题意分析
给定一个字符串和一份词典，要把字符串完整切成若干段，使每一段都是词典里的词，并把所有可行的切法都列出来，每种切法用空格连接成一个句子。返回顺序不限。
与只问「能不能切」的版本相比，这里的输出是全部方案而不是一个布尔值。这个差别很关键：判定问题的答案规模是常数，可以用线性的递推解决；而枚举问题的答案规模本身可能是指数级的，任何算法都不可能比输出规模更快。
词典中的词可以重复使用，且切分必须覆盖整个字符串、段与段之间不能重叠也不能留空。所以每种方案都可以看成在字符串上选一组切点，把它划成连续的若干段。
数据范围给得很小：字符串长度不超过 $20$，词典规模不超过 $1000$，单词长度不超过 $10$。这明确暗示了指数级的搜索是可以接受的，同时也提醒不要在切分之外做过度优化。
边界情形包括：完全无法切分，此时返回空列表而不是含空串的列表；整个字符串本身就是一个词；同一段前缀有多种不同的后续切法（这正是需要复用的地方）；以及像大量重复字符配上短词这样的极端输入，方案数会爆炸。
解法：记忆化 DFS 枚举所有后缀句子
核心思路
定义
dfs(start)：返回s[start:]能组成的所有句子。枚举当前单词的结束位置；若s[start:end]在词典中，就递归求出dfs(end)，再把当前单词接到每个后缀句子前面。不同切分路径会反复遇到同一个
start，例如“catsanddog”中的后缀“dog”。用哈希表缓存每个起点的完整结果，保证每个后缀只展开一次。之所以能缓存，是因为后缀的合法切法只由start决定，与前面如何切分无关。递归到字符串末尾时返回
[""]，表示“有一种合法完成方式，后面不再放单词”。若返回空列表，上一层即使找到最后一个合法单词，也没有对象可与它组合。本题要求输出所有方案，答案数量本身可能是指数级；记忆化消除的是重复搜索，无法消除必要的输出成本。
解题步骤
- 把词典放入哈希集合，使单词查询为均摊 $O(1)$。
- 调用
dfs(0)；进入递归时先查询缓存。- 若
start == s.length()，返回只含空字符串的列表。- 枚举
end，若当前前缀不在词典中就跳过。- 遍历
dfs(end)的所有结果：后缀为空时只加入当前单词，否则用一个空格连接。- 缓存当前起点的结果，包括空结果，最后返回。
例如
s = "catsanddog"时，起点0可选cat或cats；它们分别接上sand dog、and dog，得到两种答案。后缀dog只会计算一次。
代码实现
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> words = new HashSet<>(wordDict);
return dfs(s, 0, words, new HashMap<>());
}
private List<String> dfs(
String s,
int start,
Set<String> words,
Map<Integer, List<String>> memo
) {
if (memo.containsKey(start)) {
return memo.get(start);
}
if (start == s.length()) {
List<String> base = new ArrayList<>();
base.add("");
return base;
}
List<String> sentences = new ArrayList<>();
for (int end = start + 1; end <= s.length(); end++) {
String word = s.substring(start, end);
if (!words.contains(word)) {
continue;
}
for (String suffix : dfs(s, end, words, memo)) {
sentences.add(suffix.isEmpty()
? word
: word + " " + suffix);
}
}
memo.put(start, sentences);
return sentences;
}
}
func wordBreak(s string, wordDict []string) []string {
words := make(map[string]struct{}, len(wordDict))
for _, word := range wordDict {
words[word] = struct{}{}
}
memo := make(map[int][]string)
var dfs func(int) []string
dfs = func(start int) []string {
if sentences, ok := memo[start]; ok {
return sentences
}
if start == len(s) {
return []string{""}
}
sentences := make([]string, 0)
for end := start + 1; end <= len(s); end++ {
word := s[start:end]
if _, ok := words[word]; !ok {
continue
}
for _, suffix := range dfs(end) {
if suffix == "" {
sentences = append(sentences, word)
} else {
sentences = append(sentences, word+" "+suffix)
}
}
}
memo[start] = sentences
return sentences
}
return dfs(0)
}
复杂度分析
设 $n$ 为字符串长度，$M$ 为词典总字符数，$R$ 为所有记忆化结果中实际生成的字符串字符总量。
- 时间复杂度：$O(M+n^3+R)$。共有 $O(n)$ 个起点，每个起点枚举 $O(n)$ 个终点，截取和哈希子串最坏需要 $O(n)$；生成答案的复制成本计入 $R$。
- 空间复杂度：$O(M+n+R)$。词典、递归栈和记忆化结果分别对应这三项；最终答案也包含在 $R$ 中。
关键点总结
- 状态是“从某下标开始的全部句子”，缓存值必须是完整结果列表。
- 末尾返回
[""]是组合递归的单位元，不等同于“无解”的空列表。- 无解状态也要缓存，否则失败后缀仍会被反复搜索。
- 答案规模可能指数增长，复杂度必须按输出量描述，不能声称整体是多项式。
- 调用方不能原地修改缓存返回的列表，否则其他分支会读到被污染的数据。
易错点总结
- 基准情况返回空列表：
s = "cat"、词典含cat时也拼不出答案。- 拼接空后缀时仍添加空格：会生成末尾带空格的句子。
end上界写成小于s.length()：永远无法选中以字符串末尾结束的单词。- 只缓存有解状态：无解后缀仍会导致指数级重复搜索。
- 把本题当作判定版只存布尔值：只能知道能否拆分，无法恢复全部切法。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 139. 单词拆分 | 中等 | 只问可行性，答案规模是常数，可用一维布尔递推在多项式时间内解决 |
| 472. 连接词 | 困难 | 对每个单词做一次拆分判定，且要求至少切成两段，重点在批量处理与去重 |
| 131. 分割回文串 | 中等 | 同为枚举全部切分方案，但每段的合法性由回文判定给出而非查词典 |
| 93. 复原 IP 地址 | 中等 | 段数固定为四且每段有数值范围限制，剪枝比记忆化更关键 |
| 22. 括号生成 | 中等 | 同为输出全部方案的构造题，合法性由计数约束而非字典匹配决定 |
| 212. 单词搜索 II | 困难 | 词典匹配发生在二维网格上，需要用字典树把多词匹配合并进一次搜索 |