好的，已经记录你已学习的所有题目。这次我将为你讲解一个你未学习过的、结合了搜索与动态规划思想的经典问题。

LeetCode 140. 单词拆分 II

题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你编写程序，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

注意：

1. 词典中的同一个单词可以在分段中被重复使用多次。
2. 你可以以任意顺序返回答案。

示例 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）。

1. 我们从字符串 s 的起始位置（索引 0）开始尝试。
2. 在当前位置 start，我们尝试所有可能的结束位置 end (从 start+1 到字符串长度)。
3. 如果子串 s[start:end] 存在于字典 wordDict 中，那么我们就找到了一个合法的单词。
4. 我们记录这个单词，然后以 end 作为新的起点，递归地进行搜索。
5. 当我们恰好到达字符串末尾时，就将一路上记录的单词用空格连接起来，形成一个有效句子，加入答案列表。

但这样会存在什么问题？
对于像 "aaaaa..." 这样的字符串，字典是 ["a","aa","aaa", ...]，搜索树会非常庞大，很多不同路径的中间状态会被重复计算多次（例如，从同一个位置 i 开始往后搜索）。这会导致指数级的时间复杂度，从而超时。

第二步：引入记忆化搜索（Memoization）

为了避免重复计算，我们引入记忆化技术。

1. 我们定义一个哈希表 memo，其键（key）是当前搜索的起始索引 start，值（value）是从这个起始索引开始，能够组成的所有句子的列表。
2. 在DFS函数中，首先检查 memo[start] 是否已经计算过，如果计算过，直接返回结果，不再重复计算。
3. 只有当 memo[start] 不存在时，我们才进行计算。

这个 memo 具体记录什么？
它记录的是：从索引 start 到字符串末尾 len(s) 之间，所有可能的拆分结果（一个列表，列表的每个元素是由单词组成的列表）。

为什么能这样记忆化？
因为对于给定的起始索引 start，无论之前是如何拆分得到这个位置的，从这个位置往后的所有拆分可能性是唯一确定的。这就是所谓的“无后效性”，是动态规划能够应用的关键。

第三步：详细步骤拆解

我们以 s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] 为例。

1. 预处理：为了快速判断子串是否在字典中，我们将 wordDict 转换为一个哈希集合 wordSet。
2. 定义递归函数 dfs(start)：
   • 输入：当前搜索的起始索引 start。
   • 输出：一个列表，里面包含所有从 start 开始到末尾的有效拆分方案（每个方案本身是一个单词列表）。
   • 终止条件：
     • 如果 start == len(s)，说明我们成功到达了末尾。此时返回一个包含一个空列表的列表 [[]]，代表一种有效的拆分方案（但还没有任何单词）。
   • 递归过程：
     • 初始化一个空列表 result 用于收集从 start 开始的所有方案。
     • 从 start 开始，枚举结束位置 end (start+1 到 len(s)+1)。
     • 获取子串 word = s[start:end]。
     • 如果 word 在 wordSet 中，说明这是一个合法的单词。
       • 那么我们递归调用 dfs(end)，获取从 end 位置开始的所有后续拆分方案列表 sub_sentences。
       • 对于 sub_sentences 中的每一个后续单词列表 sub，我们构造一个新的方案：[word] + sub，并将其加入到 result 中。
     • 枚举结束后，将 result 存入 memo[start]，并返回 result。
3. 启动搜索：调用 dfs(0)，得到从位置0开始的所有拆分方案（每个方案是单词列表）。
4. 格式化输出：将每个单词列表用空格连接起来，形成最终的句子列表。

第四步：模拟运行过程

调用 dfs(0)：

• start=0，尝试 end=3，word="cat" 在集合中。
  • 调用 dfs(3)：start=3，尝试 end=6，word="san" 不在集合中。尝试 end=7，word="sand" 在集合中。
    • 调用 dfs(7)：start=7，尝试 end=10，word="dog" 在集合中。
      • 调用 dfs(10)：start=10 等于长度，返回 [[]]。
      • sub_sentences = [[]]，构造新方案 ["dog"] + [] = ["dog"]，作为 dfs(7) 的结果之一。
    • dfs(7) 的 result 为 [["dog"]]，存入 memo[7] 并返回。
    • sub_sentences = [["dog"]]，构造新方案 ["sand"] + ["dog"] = ["sand", "dog"]，作为 dfs(3) 的结果之一。
  • start=3，继续尝试 end=4... end=6，word="and" 在集合中。
    • 调用 dfs(6)：start=6，尝试 end=10，word="dog" 在集合中。
      • 调用 dfs(10)：直接返回 memo[10] 即 [[]]。
      • 构造新方案 ["dog"] + [] = ["dog"]。
    • dfs(6) 的 result 为 [["dog"]]。
    • 构造新方案 ["and"] + ["dog"] = ["and", "dog"]，作为 dfs(3) 的另一个结果。
  • dfs(3) 的最终 result 为 [["sand", "dog"], ["and", "dog"]]，存入 memo[3]。
  • sub_sentences 就是上面的结果，构造出 dfs(0) 的两个方案：
    • ["cat"] + ["sand", "dog"] = ["cat", "sand", "dog"]
    • ["cat"] + ["and", "dog"] = ["cat", "and", "dog"]
• start=0，继续尝试 end=4，word="cats" 在集合中。
  • 调用 dfs(4)：start=4，尝试 end=7，word="and" 在集合中。
    • 调用 dfs(7)：直接返回 memo[7] 即 [["dog"]]。
    • 构造新方案 ["and"] + ["dog"] = ["and", "dog"]。
  • dfs(4) 的 result 为 [["and", "dog"]]。
  • 构造新方案 ["cats"] + ["and", "dog"] = ["cats", "and", "dog"]，作为 dfs(0) 的第三个结果。
• dfs(0) 的最终结果为三个单词列表，连接起来即得到题目输出。

第五步：关键点总结

1. 记忆化的精髓：memo[start] 存储的是从 start 到末尾的所有句子（单词列表），而不是简单的 True/False。这使得我们在找到一个合法单词后，能直接拼接出完整句子，避免了重复的字符串拼接操作。
2. 与“单词拆分 I”的区别：“单词拆分 I” (LeetCode 139) 只需要判断能否拆分，用布尔值的动态规划即可。而本题需要所有具体方案，必须使用带返回结果的记忆化搜索或回溯。
3. 时间复杂度：最坏情况下，每个位置都可能是一个单词的结尾，并且需要组合所有可能。但得益于记忆化，每个子问题 (dfs(i)) 只被计算一次。最终复杂度与答案的数量成线性关系，但构造答案本身需要时间。对于无法拆分的输入，可以提前用“单词拆分 I”的方法做一个快速判断，避免无效的深度搜索。

这种方法将搜索（DFS） 与动态规划的记忆化（Memoization） 完美结合，是解决此类“输出所有方案”问题的标准且高效的范式。