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 到末尾的子串）的所有可能句子后，把结果存起来。
[*]下次如果再遇到需要计算 s 的情况，直接从缓存里取结果，不用再递归。
[*]优点：避免了重复子问题的计算，效率大幅提升。
思路三：动态规划 (Dynamic Programming)
自底向上构建解。
[*]定义 dp 为子串 s 能构成的所有句子列表。
[*]从后往前遍历，如果 s 是单词，且 dp 有解，则将 s 与 dp 中的句子组合。
[*]优点：逻辑清晰，无递归栈溢出风险。
[*]缺点：代码实现上处理字符串拼接稍显繁琐，通常记忆化搜索写起来更简洁。
高级优化：可行性剪枝
在开始生成所有句子之前，先利用 单词拆分 I (Word Break I) 的逻辑（布尔型 DP）判断一下 s 是否至少能被拆分。
[*]如果根本不能拆分，直接返回空列表 []。
[*]这可以防止在某些极端测试用例（字符串很长但无解）下超时。
3. 代码实现 (记忆化搜索)
下面提供基于 记忆化搜索 (DFS + Memo) 的 Python 3 代码。这是最通用、代码最清晰且效率较高的解法。
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List) -> List:
"""
主函数：接收字符串 s 和单词列表 wordDict，返回所有可能的句子
"""
# 1. 预处理：将 wordDict 转换为集合 (set)
# 原因：集合的查找时间复杂度是 O(1)，而列表是 O(N)，能显著加快判断速度
word_set = set(wordDict)
# 2. 创建记忆化缓存字典
# key: 起始索引 index
# value: 从该索引开始到字符串末尾，所有可能的句子列表
memo = {}
def dfs(start: int) -> List:
"""
深度优先搜索辅助函数
参数 start: 当前处理到的字符串 s 的索引位置
返回：s 部分所有可能的句子组合列表
"""
# --- 终止条件 ---
# 如果 start 达到了字符串长度，说明前面已经完美匹配完了
# 返回一个包含空字符串的列表，方便上层进行拼接
if start == len(s):
return [""]
# --- 记忆化检查 ---
# 如果这个起始位置已经计算过，直接返回缓存的结果
if start in memo:
return memo
# 存储当前起始位置的所有有效句子
sentences = []
# --- 尝试所有可能的分割点 ---
# end 从 start + 1 遍历到 len(s)，表示截取 s
for end in range(start + 1, len(s) + 1):
word = s
# 如果截取的单词在字典中
if word in word_set:
# 递归计算剩余部分 (s) 的所有句子
rest_sentences = dfs(end)
# 将当前单词与剩余部分的句子组合
for rest in rest_sentences:
if rest == "":
# 如果剩余部分是空（说明刚好到末尾），直接添加当前单词
sentences.append(word)
else:
# 否则，当前单词 + 空格 + 剩余句子
sentences.append(word + " " + rest)
# --- 存入缓存并返回 ---
memo = sentences
return sentences
# 从索引 0 开始搜索
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。
[*]dfs(3) 收到 ["dog"]，组合 "sand" + " " + "dog" -> 得到 ["sand dog"]，存入 memo。
[*]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，直接返回 []。
# 可以在 wordBreak 函数开头加入这段优化代码
def can_break(s, word_set):
n = len(s)
dp = * (n + 1)
dp = True
for i in range(1, n + 1):
for j in range(i):
if dp and s in word_set:
dp = True
break
return dp
# 使用示例：
# if not can_break(s, word_set):
# return []注：对于本题给定的数据范围（长度 20），这个优化不是必须的，但这是一个很好的工程化思维。
7. 总结
[*]核心算法：使用 DFS (深度优先搜索) 遍历所有分割可能性。
[*]关键优化：使用 Memoization (记忆化) 缓存 dfs(index) 的结果，避免重复计算子串。
[*]数据结构：将 wordDict 转为 set 以加速查找。
[*]字符串拼接：注意处理空格，当递归返回空列表表示到达末尾时，不要多加空格。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 前排留名，哈哈哈 过来提前占个楼
页:
[1]