教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文基于 AlgoNote算法通关手册中 0140. 单词拆分 II 题解 展开系统讲解如何用「回溯 记忆化搜索」在字典约束下枚举字符串的全部合法拆分句子。读完本文你将掌握一类「求所有可行解」的字符串分割题型的通用套路如何设计dfs(start)递归状态、如何用memo数组消除重复子问题、以及如何结合字典树等数据结构进一步加速单词匹配并能直接迁移到分割回文串等同类题目上。一、题目回顾在字典约束下还原所有合法句子题目编号0140. 单词拆分 IIWord Break II标签为「字典树、记忆化搜索、数组、哈希表、字符串、动态规划、回溯」难度为困难。题意概述给定一个非空字符串s和一个包含非空单词列表的字典wordDict要求在字符串中增加空格来构建句子使得句子中所有的单词都在词典中最终返回所有这些可能的句子。题目附带两条关键说明分隔时可以重复使用字典中的单词单词可复用无使用次数限制可以假设字典中没有重复的单词。与原题 0139. 单词拆分只问“能否拆分”返回布尔值不同本题要求枚举出所有拆分方案因此解空间不再是一个真/假值而是一棵完整的“分割决策树”这也是本题被标记为困难的核心原因。从 AlgoNote 的 00_05_solutions_list.md 可以看出0139 与 0140 两题在题解库中是成对收录的且 0139 在 00_06_categories_list.md 中被归入「完全背包问题」一类的练习题中而 0140 则在 0139 基础上多出了「回溯」标签——这一标签差异正好对应了“判断可行性”与“枚举全部方案”两种问题形态的解法差异。二、核心思路回溯 记忆化搜索原文档给出的解法策略非常明确回溯 记忆化搜索。其基本思想可以概括为对于字符串s如果某个位置左侧部分是单词列表中的单词则拆分出该单词然后对s右侧剩余部分进行递归拆分如果可以将整个字符串s拆分成单词列表中的单词则得到一个合法句子使用memo数组进行记忆化存储减少重复计算。2.1 为什么单纯回溯会超时从回溯的视角看本题的解空间是所有可能的分割点组合。以s pineapplepenapple、字典含[apple, pen, applepen, pine, pineapple]为例pine之后既可以继续拆applepen也可以先拆apple再拆pen——同一段剩余后缀会被多次作为子问题求解。如果只做朴素回溯每层枚举所有分割点、递归后再枚举下一层同一后缀s[i:]的拆分方案会被反复计算产生大量重复子问题时间开销呈指数级增长。这正是需要引入记忆化搜索的原因。2.2 记忆化搜索动态规划的自顶向下实现AlgoNote 的 记忆化搜索专题 给出了精确定义记忆化搜索是一种通过存储已经遍历过的状态信息从而避免对同一状态重复遍历的搜索算法属于动态规划的一种实现方式。当算法需要计算某个子问题的结果时首先检查是否已经计算过该问题如果已经计算过则直接返回存储的结果否则计算并存储下来以备将来使用。该专题还给出了记忆化搜索的通用四步法写出动态规划的「状态」和「状态转移方程」定义一个缓存数组或哈希表用于保存子问题的解定义递归函数先查缓存命中则直接返回未命中则计算并存入缓存在主函数中调用递归函数并返回结果。本题正是这一模板的直接应用dfs(start)表示「求解s[start:]的所有合法拆分方案」memo[start]缓存该后缀的拆分结果同一后缀只需计算一次。三、源码级拆解逐行理解原文档代码以下是原文档给出的完整可运行实现来自 word-break-ii.mdclass Solution: def wordBreak(self, s: str, wordDict: List[str]) - List[str]: size len(s) memo [None for _ in range(size 1)] def dfs(start): if start size - 1: return [[]] if memo[start]: return memo[start] res [] for i in range(start, size): word s[start: i 1] if word in wordDict: rest_res dfs(i 1) for item in rest_res: res.append([word] item) memo[start] res return res res dfs(0) ans [] for item in res: ans.append( .join(item)) return ans3.1 状态设计与缓存初始化size len(s)记录字符串长度memo [None for _ in range(size 1)]memo[start]存放s[start:]的全部合法拆分方案每个方案是一个单词列表。用None作为“未计算”的哨兵值与「拆不出任何方案时的空列表[]」区分开——这是一个容易被忽略的关键细节如果直接用空列表表示未计算将无法区分「未计算」与「该后缀确实无解」从而可能导致错误或重复计算。3.2 递归终止条件if start size - 1: return [[]]当start越过最后一个字符即s[start:]为空串时说明前面的单词已经恰好拼接完整个字符串此时只有一种“空方案”返回[[]]包含一个空列表的列表。这个[[]]是方案拼接的基础上层[word] item中的item为空列表时恰好组成[word]从而逐层累积出完整方案。3.3 枚举分割点与回溯for i in range(start, size): word s[start: i 1] if word in wordDict: rest_res dfs(i 1) for item in rest_res: res.append([word] item)枚举i从start到size - 1逐个尝试切分子串s[start: i 1]作为当前单词用word in wordDict做字典匹配哈希表查单词平均 $O(1)$只有命中字典才继续递归对每个合法切分递归求解后缀s[i 1:]的方案rest_res并把当前单词word拼接到每个方案头部构成完整方案这里res.append([word] item)本质上是“做选择”而循环遍历到下一个i就是“撤销选择、尝试下一分支”——与回溯算法「选择 - 递归 - 回溯」的通用模式一致可对照 回溯算法专题 中的通用模板理解。3.4 结果格式化递归完成后res即dfs(0)中每个元素是单词列表[pine, apple, pen, apple]最后通过 .join(item)拼接成带空格的句子字符串返回得到题目要求的List[str]输出。3.5 时间复杂度分析时间复杂度最坏情况下例如s全由a组成、字典含a、aa等合法拆分方案数为指数级近似卡特兰数/斐波那契数量级因此最坏复杂度为指数级这是「枚举全部方案」类题目的固有代价无法避免空间复杂度$O(n \times k)$ 量级其中n为字符串长度k为方案数量级——memo需要存储所有后缀的拆分方案递归栈深度不超过n。需要强调的是虽然最坏情况仍是指数级但记忆化保证了「同一后缀只计算一次」避免了朴素回溯中重复子问题被反复求解的浪费这也是本题从“朴素回溯必超时”到“可 AC”的关键优化。四、纵深拓展两处可落地的工程化优化4.1 用字典树替代哈希集合加速前缀匹配原题解标签中排在第一位的是「字典树」。当字典规模很大0139 题解给出的约束是wordDict.length可达 1000、单词长度可达 20且由小写字母组成时逐一切分再查哈希表虽然平均复杂度仍可接受但前缀剪枝能力弱哈希表无法告诉我们“从start出发哪些前缀可能是单词”必须枚举完所有i才能确定。而字典树Trie天然支持前缀匹配从根节点沿字符路径下行只要某个字符不存在对应子节点就可以立刻停止扩展当前前缀从而剪掉大量不可能命中的分割点。AlgoNote 的 字典树专题 指出字典树是“利用字符串公共前缀、将相同前缀的单词合并存储”的树形结构根节点不存字符每个单词结尾节点用isEnd标记。仓库中的完整实现位于 string_trie.py其核心结构为class Node: # 字符节点 def __init__(self): # 初始化字符节点 self.children dict() # 初始化子节点 self.isEnd False # isEnd 用于标记单词结束 class Trie: # 字典树 def __init__(self): # 初始化字典树 self.root Node() # 根节点不保存字符 def insert(self, word: str) - None: ... # 遍历字符、逐层建节点结尾置 isEnd True def search(self, word: str) - bool: ... # 沿路径查找最终判断 cur.isEnd def startsWith(self, prefix: str) - bool: ... # 沿路径查找前缀无需 isEnd 判断将上述结构移植进本题可以把dfs内层的枚举改写为从start出发沿 Trie 下行边扩展边检查cur.isEnd一旦命中单词结尾就递归dfs(i 1)一旦字符不匹配就break。这样单词匹配与前缀剪枝被合二为一在长串、大字典场景下能显著减少无效切分尝试。这也可以解释为什么题目标签把「字典树」放在最前面——它是本题在基础解法之上最自然的进阶优化方向。4.2 与 0139 单词拆分的对比从可行性判定到方案枚举本题是 0139. 单词拆分 的进阶版。0139 的题解采用自底向上的动态规划class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: size len(s) dp [False for _ in range(size 1)] dp[0] True for i in range(size 1): for j in range(i): if dp[j] and s[j: i] in wordDict: dp[i] True return dp[size]该解法定义dp[i]表示长度为i的前缀s[0: i]能否拆分成单词状态转移为dp[j] True且s[j: i]在字典中则dp[i] True时间复杂度 $O(n^2)$、空间复杂度 $O(n)$。对比可见维度0139 单词拆分0140 单词拆分 II返回内容单个布尔值能否拆分所有合法句子列表状态粒度dp[i]只需记录可/不可memo[start]需缓存全部方案主要算法自底向上动态规划递推自顶向下回溯 记忆化搜索最坏复杂度$O(n^2)$指数级方案数本身指数级这正是 记忆化搜索专题 中所阐述的「记忆化搜索与递推」的分工当状态转移方程复杂、且需要显式枚举路径时自顶向下的记忆化搜索天然更契合而仅做可行性判断时递推更简洁高效。五、实战演练手写一个可运行的最小实现为了便于读者在本地验证这里给出一个不依赖题解环境、可直接复制运行的完整版本在 Python 3 环境下执行from typing import List class Solution: def wordBreak(self, s: str, wordDict: List[str]) - List[str]: word_set set(wordDict) # 转为哈希集合加速单词查询 size len(s) memo [None for _ in range(size 1)] # None 表示尚未计算 def dfs(start: int) - List[List[str]]: if start size: # 空后缀返回唯一空方案 return [[]] if memo[start] is not None: # 命中缓存直接返回 return memo[start] res [] for i in range(start, size): word s[start: i 1] if word in word_set: for tail in dfs(i 1): res.append([word] tail) memo[start] res # 记录当前后缀的全部方案 return res return [ .join(words) for words in dfs(0)] if __name__ __main__: s pineapplepenapple wordDict [apple, pen, applepen, pine, pineapple] print(Solution().wordBreak(s, wordDict)) # 输出示例 # [pine apple pen apple, pineapple pen apple, pine applepen apple]将wordDict改为set可将单词查询从线性退化风险降到哈希平均 $O(1)$start size与原文start size - 1等价逻辑上更直观。读者可以自行替换输入s catsandog、wordDict [cats, dog, sand, and, cat]验证「无解时返回空列表」的行为此时dfs(0)返回[]memo中大量[]缓存会避免重复的无解搜索。六、同型题目迁移回溯分割类题的通法「回溯 记忆化或剪枝」的组合不仅适用于本题也是 AlgoNote 题解库中一类分割/组合枚举题的通用骨架。一个高度相似的例子是 0131. 分割回文串它同样是「从左到右枚举分割点 递归 撤销选择」的框架区别仅在于合法性判断本题用word in wordDict判断切出的子串是否为字典单词而分割回文串用isPalindrome(s, start_index, i)判断子串是否为回文终止条件也一致start_index len(s)时把当前path方案收进结果集。两者的框架对比如下# 单词拆分 II 的分支约束 if s[start: i 1] in word_set: # 选择当前单词 - 递归 dfs(i 1) - 由循环自然切换下一分支 # 分割回文串的分支约束见 docs/solutions/0100-0199/palindrome-partitioning.md if self.ispalindrome(s, start_index, i): self.path.append(s[start_index: i 1]) # 做选择 self.backtrack(s, i 1) # 递归 self.path.pop() # 撤销选择回溯建议读者对照阅读这两篇题解把「分割点枚举 合法性剪枝 递归收集方案」提炼成自己的模板即可覆盖 LeetCode 上一大批「求所有分割/组合方案」的困难题。七、总结本文以 AlgoNote 的 0140. 单词拆分 II 题解 为核心完成了从题意、思路、逐行代码到优化与迁移的完整讲解要点归纳如下问题本质在单词可重复使用的字典约束下枚举字符串的全部合法空格切分句子属于「求所有可行解」的枚举问题最坏方案数为指数级核心解法dfs(start)自顶向下递归 memo数组记忆化用None哨兵区分「未计算」与「无解」同一后缀只求解一次进阶优化可将哈希集合升级为字典树见 string_trie.py在枚举分割点的同时完成前缀剪枝姊妹题对比0139 单词拆分用自底向上 DP 只判可行性$O(n^2)$0140 必须回溯枚举全部方案二者互补构成完整的「单词拆分」双题同类题如 0131 分割回文串可直接复用本框架。如果希望在 AlgoNote 中进一步延伸学习建议按以下路径阅读先掌握 回溯算法专题 的「选择 - 递归 - 撤销选择」模板再通读 记忆化搜索专题 理解「自顶向下 DP」的本质最后回到 0139 单词拆分 对比两种形态的差异即可完整吃透这一考点组合。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 140 单词拆分 II 题解从暴力回溯到笛卡尔积记忆化优化LeetCode 140 单词拆分 II 题解从暴力回溯到笛卡尔积记忆化优化 导读 本文围绕 LeetCode 140「单词拆分 IIWord Break文档教程知识库AlgoNote 题解精讲0090. 子集 II —— 含重复元素的子集枚举排序去重 回溯 / 二进制枚举AlgoNote 题解精讲0090. 子集 II —— 含重复元素的子集枚举排序去重 回溯 / 二进制枚举 本篇是「算法通关手册」AlgoNote教程文档知识库LeetCode 78 子集Subsets回溯解法精讲从回溯模板到幂集枚举LeetCode 78 子集Subsets回溯解法精讲从回溯模板到幂集枚举 导读 LeetCode 78「子集」要求给定一组不含重复元素的整数数组 num文档教程知识库上一篇如何快速上手location-to-phone-number从手机号定位到地图导航的零基础入门教程下一篇GoogleTest 开源项目入门指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
