§1

题目描述

给定字符串 s 和词典 wordDict,返回所有「用词典单词拼接恰好等于 s」的句子(单词间用空格隔开)。顺序不限。

输入 = s="catsanddog", dict=[cat,cats,and,sand,dog]　输出 = ["cats and dog","cat sand dog"]

输入 = s="catsandog", dict=[cats,dog,sand,and,cat]　输出 = [](尾部 "og" 拼不出)

§2

思路解析动画文字版

记住「枚举词典词切首段、递归拼后缀、memo 缓存起点结果」,下面看调用栈逐层展开。

调用 dfs(0):求从下标 0(灰色之后)开始能拼出的所有句子,压入调用栈。

在 dfs(0) 里试切词 "cat"(下标 0 到 2):它在词典里!接着递归 dfs(3) 求后缀 "sanddog" 的所有句子。

调用 dfs(3):求从下标 3(灰色之后)开始能拼出的所有句子,压入调用栈。

在 dfs(3) 里试切词 "sand"(下标 3 到 6):它在词典里!接着递归 dfs(7) 求后缀 "dog" 的所有句子。

调用 dfs(7):求从下标 7(灰色之后)开始能拼出的所有句子,压入调用栈。

在 dfs(7) 里试切词 "dog"(下标 7 到 9):它在词典里!接着递归 dfs(10) 求后缀 "" 的所有句子。

调用 dfs(10):求从下标 10(灰色之后)开始能拼出的所有句子,压入调用栈。

i=10 已到串尾,说明前面的词正好把整串拼完。直接返回 [""](一个空句子,成功标记),这是递归出口,不写入 memo。

dfs(10) 返回 1 个后缀句子,把 "dog" 拼到每个前面,dfs(7) 目前收集到 1 个句子。

dfs(7) 的所有切法试完,得到 1 个句子,写入 memo[7] 并返回,弹出调用栈。

dfs(7) 返回 1 个后缀句子,把 "sand" 拼到每个前面,dfs(3) 目前收集到 1 个句子。

dfs(3) 的所有切法试完,得到 1 个句子,写入 memo[3] 并返回,弹出调用栈。

dfs(3) 返回 1 个后缀句子,把 "cat" 拼到每个前面,dfs(0) 目前收集到 1 个句子。

在 dfs(0) 里试切词 "cats"(下标 0 到 3):它在词典里!接着递归 dfs(4) 求后缀 "anddog" 的所有句子。

调用 dfs(4):求从下标 4(灰色之后)开始能拼出的所有句子,压入调用栈。

在 dfs(4) 里试切词 "and"(下标 4 到 6):它在词典里!接着递归 dfs(7) 求后缀 "dog" 的所有句子。

到达 dfs(7),memo[7] 已有缓存,直接返回,不再展开(这正是记忆化省时的关键)。

dfs(7) 返回 1 个后缀句子,把 "and" 拼到每个前面,dfs(4) 目前收集到 1 个句子。

dfs(4) 的所有切法试完,得到 1 个句子,写入 memo[4] 并返回,弹出调用栈。

dfs(4) 返回 1 个后缀句子,把 "cats" 拼到每个前面,dfs(0) 目前收集到 2 个句子。

dfs(0) 的所有切法试完,得到 2 个句子,写入 memo[0] 并返回,弹出调用栈。

调用栈全部弹空,dfs(0) 返回最终答案:共 2 个句子:"cat sand dog"、"cats and dog"。记忆化让每个起点只算一次,把可能指数级的重复展开压了下来。

边界:整串是词返回它;拼不通返回空;单字符同理。

两个延伸:先 I 判可行性剪枝;II 求方案故需记忆化返回列表。

§3

参考代码

from typing import Listfrom functools import lru_cacheclass Solution:    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:        words = set(wordDict)        @lru_cache(None)        def dfs(i: int):            if i == len(s):                return ['']            ans = []            for j in range(i + 1, len(s) + 1):                word = s[i:j]                if word in words:                    for tail in dfs(j):                        ans.append(word if not tail else word + ' ' + tail)            return ans        return dfs(0)

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间：O(n³ + 输出量)，n 是串长。每个起点 i 只算一次(记忆化),但内层枚举右端 j、且每次都要构造并哈希子串 s[i..j)(本身就要 O(j−i) 的时间),所以光「枚举 + 查词」就是 O(n³)(也可记最大词长 L、写成 O(n²·L));若不计子串构造、只看集合查询才是 O(1)。再加上合法句子可能指数级,拼接与收集的代价取决于输出量,故整体 O(n³ + 输出量)
空间：O(n + 输出量)，递归深度 O(n),memo 与最终句子列表占「输出量」级空间

§5

易错点

✗ 错误写法：不加 memo,纯回溯重复展开

✓ 正确写法：用 memo[i] 缓存每个起点的句子列表

同一个后缀起点会被多条前缀反复递归到;不缓存会退化成指数级重复计算,加 memo 后每个起点只算一次

✗ 错误写法：拼接时无脑加空格

✓ 正确写法：tail 为空(到结尾)时不加空格

dfs(n) 返回的空串代表「正好拼完」,若拼成 "词 + 空格 + 空串" 会多出尾部空格;判 tail 是否为空决定加不加

✗ 错误写法：只判断能否拆分(返回布尔)

✓ 正确写法：本题要返回所有具体句子

这是「单词拆分 II」,要列出全部拼法;若只需判断可行性(I)用布尔 DP 即可,但这里得收集句子列表

面试追问把动画讲成自己的话

追问能不能先用「单词拆分 I」判断有没有解,再决定要不要枚举句子?

可以,而且是常见优化。先用一遍 O(n²) 的布尔 DP 判断 s 整体能否被拆分;若不能,直接返回空列表,省去可能很深的无效递归(典型如 "aaaa...aab" 这种大量前缀可拼、但尾部死路的退化数据)。能拆分时再跑记忆化 DFS 收集所有句子。这个「先可行性剪枝、再枚举」的两段式能避免最坏情况的无谓展开。

追问为什么这道题不能像普通 DP 那样只用一维布尔数组解决?

「单词拆分 I」只问能否拆分,答案是布尔,一维 DP 足够。但 II 要列出所有具体句子,句子数量可能指数级,无法压进布尔或计数的 DP 状态里,必须真正地把每个起点的句子列表构造出来,所以用「记忆化 DFS 返回列表」而不是「布尔 DP」。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 动态规划套路 57/64

地下城游戏

LeetCode 174 · 困难 · 沿着动态规划套路继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

599道动画图解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

from typing import Listfrom functools import lru_cacheclass Solution: def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: words = set(wordDict) @lru_cache(None) def dfs(i: int): if i == len(s): return [''] ans = [] for j in range(i + 1, len(s) + 1): word = s[i:j] if word in words: for tail in dfs(j): ans.append(word if not tail else word + ' ' + tail) return ans return dfs(0)