给定一个字符串
s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。注意：词典中的同一个单词可能在分段中被重复使用多次。
示例 1：
示例 2：
示例 3：
说明：
1 <= s.length <= 20
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 10
s和wordDict[i]仅有小写英文字母组成
wordDict中所有字符串都 不同
这题的核心难点不是判断某个前缀是不是单词，而是同一个后缀会被不同的前缀路径反复求解。
比如
catsanddog 中，当我们先选 cat 后，会去求解 sanddog；当我们先选 cats 后，会去求解 anddog。在更极端的例子里，像 "aaaaaaa..." 配合 ["a", "aa", "aaa", ...]，大量后缀会被反复递归，朴素回溯会爆炸。解法一：回溯 DFS —— 枚举每一个可行前缀
最直观的想法是：从当前位置
start 开始，枚举所有可能的前缀 s[start:end]。如果这个前缀在词典里，就把它加入当前路径，然后递归处理剩余部分 s[end:]。当
start == len(s) 时，说明整个字符串都已经被成功拆完，把当前路径拼成一个句子加入结果。这个解法的 intuition 很自然：我们在构造一棵搜索树。每一层选择一个词典单词作为当前句子的下一个 token，直到刚好覆盖整个字符串。
但它的问题也很明显：没有缓存。相同的后缀会被重复处理很多次。
Walk Through Example
以：
从下标
0 开始，既可以选 "cat"，然后继续拆 "sanddog"；也可以选 "cats"，然后继续拆 "anddog"。路径 "cat" -> "sand" -> "dog" 形成 "cat sand dog"，路径 "cats" -> "and" -> "dog" 形成 "cats and dog"。复杂度分析
设
n = len(s)。- 时间复杂度：
最坏情况下，字符串的每个位置都可以选择切或不切，合法拆分数量本身就是指数级。因此时间复杂度最坏是
O(n * 2^n)其中
2^n 来自拆分方案数量，额外的 n 来自构造句子字符串。- 空间复杂度：最坏也是指数级，如果把输出结果计入空间，因为需要存储所有句子。若不计输出，递归栈和当前路径是
O(n)。
解法二：记忆化搜索 (推荐)
朴素回溯的重复计算来自：从同一个下标
start 开始，后面能组成哪些句子，是固定的，和前面怎么走到这里无关。所以我们定义
dfs(start)表示：从 s[start:] 开始，能拆出的所有句子列表。如果
dfs(start) 已经算过，就直接返回缓存结果。这就是 Top-down DP / 记忆化搜索。注意这里缓存的不是
True / False，而是从当前下标开始可以生成的所有句子。因为这题不是判断能不能拆，而是要返回所有拆法。核心转移
从
start 出发，我们枚举 end：word = s[start:end]如果
word 在词典里，那么递归求 suffix_sentences = dfs(end)然后把当前
word 接到每个后缀句子前面。如果后缀为空，说明
word 本身就是句子的最后一个词；否则拼成 word + " " + suffix记忆化搜索天然带剪枝。
如果某个后缀无法拆分，比如
s[i:] 没有任何合法句子，那么 dfs(i) 会返回空列表 [] 并缓存下来。之后任何路径再次来到下标 i，都可以直接知道这条后缀无解，不会重复搜索。这也是为什么更适合 Top-down memo，而不是单纯从前往后硬填表。尤其在不能拆分的长字符串里，记忆化搜索可以更早停掉大量无效分支。
复杂度分析
- 时间复杂度: 最坏仍然是
O(n * 2^n)
原因是这题必须返回所有句子。最坏情况下，合法句子的数量就是指数级，任何算法都无法低于输出规模。
- 空间复杂度: 也是
O(n * 2^n)
主要来自 memo 中缓存的句子列表，以及最终答案本身。递归栈额外是
O(n)。记忆化搜索不会改变最坏复杂度的指数本质，但会显著减少重复子问题。
解法三：Bottom-up DP
定义
dp[i] = 从 s[i:] 可以拆出的所有句子, 那答案就是 dp[0]。Base case 是
dp[n] = [""]，表示空后缀可以构成一个空句子，方便前面的单词拼接。然后从右往左枚举
i，再枚举 end。如果 s[i:end] 是词典单词，就把它和 dp[end] 里的所有后缀句子拼起来。这其实是把记忆化搜索里的
dfs(start) 反过来写成表格，从后往前构造句子列表。记忆化搜索是需要 dfs(start) 时再计算，而Bottom-up DP 是先把所有 dp[i] 按依赖顺序算好
由于
dp[i] 依赖 dp[end]，而 end > i，所以我们从右往左填表。复杂度分析
- 时间复杂度: 最坏是
O(n * 2^n)
- 空间复杂度: 最坏是
O(n * 2^n)
原因和记忆化搜索一样：最坏情况下需要生成并存储指数级数量的句子。
解法四：Trie 优化 —— 用前缀树加速单词匹配
前面几种写法判断一个子串是否在词典里，通常是
s[start:end] in wordSet这已经是平均
O(1) 的哈希查找，但它仍然需要不断创建子串。对于大量前缀匹配，Trie 可以更自然地表达：从某个起点开始，沿着 Trie 往下走，只要当前字符路径不存在，就可以立刻停止。
Trie 的优势不是改变最坏复杂度，因为最终输出仍然可能是指数级；它的价值在于更早停止不可能成为单词的前缀，减少无效 substring 枚举。
如果词典里没有任何单词以
"catsx" 为前缀，那么从 s[start:] 往后扫到 "catsx" 时，就可以直接 break，不需要继续尝试更长的子串。这正是 Trie 擅长的事情：prefix pruning。下面用 Trie + 记忆化搜索写法，结构上仍然以
dfs(start) 为主，只是枚举前缀时不再反复切片查 set，而是沿 Trie 走。复杂度分析
- 时间复杂度: 最坏仍然是
O(n * 2^n)
- 空间复杂度:
O(n * 2^n + L)
Trie 本身需要额外空间，约为词典中所有单词字符总数。设词典总字符数为
L，Trie 空间是 O(L)Trie 优化更适合词典很大、前缀共享明显，或者希望避免大量无效子串检查的场景。
总结
这题要求返回所有拆分句子，所以复杂度不可能低于输出规模。最坏情况下，比如
s = "aaaa..."，词典里有 "a"、"aa"、"aaa"...，每个位置都可以切或不切，合法句子数量本身就是指数级。解法：
- 朴素回溯直接枚举所有拆分路径，但会重复求解相同后缀。
- 记忆化搜索 和 Bottom-up DP 等价，把计算结果缓存起来，避免大量重复后缀计算。
- Trie 优化没有改变指数级输出规模，但它能更高效地做前缀匹配，并且遇到不可能的前缀时立刻停止。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-140-单词拆分-ii
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 138] 随机链表的复制
下一篇
[Leetcode 143] 重排链表