LeetCode 140 单词拆分 II（输出所有可行拆分句子）：python3 题解

目录

• 140. 单词拆分 II - 完整题解
  
  
  
  • 1. 题目理解
    
  • 2. 解题思路分析
    
    
    
    • 思路一：回溯法 (Backtracking / DFS)
      
    • 思路二：记忆化搜索 (Memoization) —— 推荐解法
      
    • 思路三：动态规划 (Dynamic Programming)
      
    • 高级优化：可行性剪枝
      
    
    
  • 3. 代码实现 (记忆化搜索)
    
  • 4. 代码详解与逻辑图解
    
  • 5. 复杂度分析
    
  • 6. 进阶优化：可行性剪枝 (可选)
    
  • 7. 总结
    
  
  

140. 单词拆分 II - 完整题解

1. 题目理解

题目大意：
给你一个字符串 s 和一个单词字典 wordDict。你需要在 s 中插入空格，把它变成一个个句子，要求句子里的每一个单词都必须存在于字典 wordDict 中。你需要返回所有可能的句子组合。
关键点：

• 所有可能：这意味着不能找到一个解就停止，必须找出所有合法的分割方式。
  
• 重复使用：字典里的单词可以重复使用。
  
• 顺序：返回的句子顺序任意。
  

示例分析：
输入：s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]

• 第一种分法："cats" + "and" + "dog" -> "cats and dog"
  
• 第二种分法："cat" + "sand" + "dog" -> "cat sand dog"
  
• 输出：["cats and dog", "cat sand dog"]
  

2. 解题思路分析

这道题是经典的搜索 + 记忆化问题。我们可以把它想象成“切绳子”：我们要把字符串 s 切成若干段，每一段都必须是字典里的单词。
思路一：回溯法 (Backtracking / DFS)

最直观的想法是从字符串的开头开始，尝试截取不同长度的前缀。

• 如果前缀在字典里，就把它当作第一个单词，然后对剩下的字符串递归进行同样的操作。
  
• 如果剩下的字符串也能被完全分割，那么我们就找到了一个合法的句子。
  
• 缺点：如果不加优化，会有大量的重复计算。例如字符串 "aaaa..."，每次递归都会重新计算后面部分的可能性。
  

思路二：记忆化搜索 (Memoization) —— 推荐解法

在回溯法的基础上，我们增加一个“缓存”（字典或数组）。

• 当我们计算过 s[i:]（从索引 i 到末尾的子串）的所有可能句子后，把结果存起来。
  
• 下次如果再遇到需要计算 s[i:] 的情况，直接从缓存里取结果，不用再递归。
  
• 优点：避免了重复子问题的计算，效率大幅提升。
  

思路三：动态规划 (Dynamic Programming)

自底向上构建解。

• 定义 dp 为子串 s[i:] 能构成的所有句子列表。
  
• 从后往前遍历，如果 s[i:j] 是单词，且 dp[j] 有解，则将 s[i:j] 与 dp[j] 中的句子组合。
  
• 优点：逻辑清晰，无递归栈溢出风险。
  
• 缺点：代码实现上处理字符串拼接稍显繁琐，通常记忆化搜索写起来更简洁。
  

高级优化：可行性剪枝

在开始生成所有句子之前，先利用 单词拆分 I (Word Break I) 的逻辑（布尔型 DP）判断一下 s 是否至少能被拆分。

• 如果根本不能拆分，直接返回空列表 []。
  
• 这可以防止在某些极端测试用例（字符串很长但无解）下超时。
  

3. 代码实现 (记忆化搜索)

下面提供基于 记忆化搜索 (DFS + Memo) 的 Python 3 代码。这是最通用、代码最清晰且效率较高的解法。

1. from typing import List
3. class Solution:
4.     def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
5.         """
6.         主函数：接收字符串 s 和单词列表 wordDict，返回所有可能的句子
7.         """
8.         # 1. 预处理：将 wordDict 转换为集合 (set)
9.         # 原因：集合的查找时间复杂度是 O(1)，而列表是 O(N)，能显著加快判断速度
10.         word_set = set(wordDict)
11.         
12.         # 2. 创建记忆化缓存字典
13.         # key: 起始索引 index
14.         # value: 从该索引开始到字符串末尾，所有可能的句子列表
15.         memo = {}
17.         def dfs(start: int) -> List[str]:
18.             """
19.             深度优先搜索辅助函数
20.             参数 start: 当前处理到的字符串 s 的索引位置
21.             返回：s[start:] 部分所有可能的句子组合列表
22.             """
23.             # --- 终止条件 ---
24.             # 如果 start 达到了字符串长度，说明前面已经完美匹配完了
25.             # 返回一个包含空字符串的列表，方便上层进行拼接
26.             if start == len(s):
27.                 return [""]
28.             
29.             # --- 记忆化检查 ---
30.             # 如果这个起始位置已经计算过，直接返回缓存的结果
31.             if start in memo:
32.                 return memo[start]
33.             
34.             # 存储当前起始位置的所有有效句子
35.             sentences = []
36.             
37.             # --- 尝试所有可能的分割点 ---
38.             # end 从 start + 1 遍历到 len(s)，表示截取 s[start:end]
39.             for end in range(start + 1, len(s) + 1):
40.                 word = s[start:end]
41.                
42.                 # 如果截取的单词在字典中
43.                 if word in word_set:
44.                     # 递归计算剩余部分 (s[end:]) 的所有句子
45.                     rest_sentences = dfs(end)
46.                     
47.                     # 将当前单词与剩余部分的句子组合
48.                     for rest in rest_sentences:
49.                         if rest == "":
50.                             # 如果剩余部分是空（说明刚好到末尾），直接添加当前单词
51.                             sentences.append(word)
52.                         else:
53.                             # 否则，当前单词 + 空格 + 剩余句子
54.                             sentences.append(word + " " + rest)
55.             
56.             # --- 存入缓存并返回 ---
57.             memo[start] = sentences
58.             return sentences
60.         # 从索引 0 开始搜索
61.         return dfs(0)

复制代码

4. 代码详解与逻辑图解

为了让你更明白代码是如何运行的，我们以示例 s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] 为例。

• 初始调用 dfs(0)。
  
• 第一轮循环 (start=0)：
  
  
  
  • 截取 "c" (不在字典)
    
  • 截取 "ca" (不在字典)
    
  • 截取 "cat" (在字典) -> 递归调用 dfs(3) (处理 "sanddog")
    
  • 截取 "cats" (在字典) -> 递归调用 dfs(4) (处理 "anddog")
    
  • ...
    
  
  
• 递归深入 (dfs(3) 处理 "sanddog")：
  
  
  
  • 尝试 "s", "sa", "san"...
    
  • 截取 "sand" (在字典) -> 递归调用 dfs(7) (处理 "dog")
    
  
  
• 递归深入 (dfs(7) 处理 "dog")：
  
  
  
  • 截取 "dog" (在字典) -> 递归调用 dfs(10)
    
  
  
• 触底 (dfs(10))：
  
  
  
  • start == len(s)，返回 [""]。
    
  
  
• 回溯组合：
  
  
  
  • dfs(7) 收到 [""]，组合 "dog" + " " + "" -> 得到 ["dog"]，存入 memo[7]。
    
  • dfs(3) 收到 ["dog"]，组合 "sand" + " " + "dog" -> 得到 ["sand dog"]，存入 memo[3]。
    
  • dfs(0) 收到 ["sand dog"]，组合 "cat" + " " + "sand dog" -> 得到 ["cat sand dog"]。
    
  
  
• 同理，另一条路径 "cats" 会生成 "cats and dog"。
  
• 最终 dfs(0) 返回 ["cat sand dog", "cats and dog"]。
  

5. 复杂度分析

假设字符串 s 的长度为 \(N\)，字典中单词的最大长度为 \(L\)。

• 时间复杂度: \(O(2^N \cdot N)\) 在最坏情况下（例如 s="aaaaa", dict=["a"]），每个字符都可以选择切或不切。但在加入记忆化后，每个子问题 dfs(i) 只计算一次。对于每个 i，我们需要遍历最多 \(L\) 个长度的单词，并且需要拼接字符串。实际运行效率远优于纯指数级，通常可以视为 \(O(N \cdot 2^N)\) 或更优，取决于解的数量。对于本题 \(N \le 20\)，完全可以通过。
  
• 空间复杂度: \(O(2^N \cdot N)\)。主要用于存储记忆化缓存 memo 和递归调用栈。最坏情况下，所有可能的句子都需要存储。
  

6. 进阶优化：可行性剪枝 (可选)

虽然上面的代码对于 \(N \le 20\) 已经足够快，但在某些更严格的限制下（例如 \(N\) 更大），如果字符串根本无法拆分，记忆化搜索仍然会尝试所有组合直到最后才发现不行。
我们可以先运行一次 单词拆分 I 的逻辑（布尔 DP），如果返回 False，直接返回 []。

1.     # 可以在 wordBreak 函数开头加入这段优化代码
2.     def can_break(s, word_set):
3.         n = len(s)
4.         dp = [False] * (n + 1)
5.         dp[0] = True
6.         for i in range(1, n + 1):
7.             for j in range(i):
8.                 if dp[j] and s[j:i] in word_set:
9.                     dp[i] = True
10.                     break
11.         return dp[n]
13.     # 使用示例：
14.     # if not can_break(s, word_set):
15.     #     return []

复制代码

注：对于本题给定的数据范围（长度 20），这个优化不是必须的，但这是一个很好的工程化思维。
7. 总结

• 核心算法：使用 DFS (深度优先搜索) 遍历所有分割可能性。
  
• 关键优化：使用 Memoization (记忆化) 缓存 dfs(index) 的结果，避免重复计算子串。
  
• 数据结构：将 wordDict 转为 set 以加速查找。
  
• 字符串拼接：注意处理空格，当递归返回空列表表示到达末尾时，不要多加空格。
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！