单词拆分 II

这道题到底要把 s 拆出什么

给字符串 s 和词典 wordDict，把 s 切成若干段、每段是词典单词、拼回 s，列出所有句子。s="catsanddog"、词典 [cat,cats,and,sand,dog] 拼成 "cats and dog" 和 "cat sand dog"；拼不出（如 "catsandog"）返回 []。不是判定题。

把所有切法枚举一遍为什么会炸

每个位置都能切一刀或往下走，二选一分叉，切法随串长指数膨胀，数不完。更亏的是同一截后缀被反复重算：不同前缀走到同一位置，剩下那段被从头重拆。把「某位置起能拼哪些句子」算一次存下复用，重复展开就压下去。

状态定成「从下标 i 起能拼出的所有句子」

递归函数 dfs(i)（递归即函数调用自己、拆成同类小问题）：返回后缀 s[i..] 能拼出的所有句子，答案是 dfs(0)。

为什么按起点 i 记账？后缀能拼哪些句子只跟起点下标有关，跟前缀怎么走到无关："cat" 或 "cats" 走到下标 7，剩下的 "dog" 拼法都一样。给每个起点配 memo[i]（记忆化：算过的句子列表存下、下次直接取），起点只 n+1 个、各算一次。

枚举前缀词递归后缀，空串为什么是成功标记

dfs(i) 从 i 往右枚举右端 j 取前缀词 s[i..j)；词典先塞进哈希集合（O(1) 判断词在不在），词在里面就递归 dfs(j) 求后缀、把每句拼到词后。后缀非空拼「词 + 空格 + 后缀」，空串就只留词。

递归出口在 i 等于串长 n：整串拼满，返回只含空串的列表 ['']，这是「拼完了」的成功标记，让上层的词有东西可接。若某起点一个词都接不出返回 []，才是此路不通。[''] 有一个空句子、[] 一个都没有。

拿 catsanddog 亲手走一遍调用栈

顺着调用栈（函数一层层调自己形成的那摞调用）走：s="catsanddog"。dfs(0) 试 "cat" 递归 dfs(3)，dfs(3) 试 "sand"（下标 3 到 7）递归 dfs(7)，dfs(7) 试 "dog" 递归 dfs(10)，dfs(10) 到串尾返回 ['']。

往回拼：dfs(7) 得 ["dog"] 存 memo[7]，dfs(3) 拼 "sand"，dfs(0) 收到 "cat sand dog"。dfs(0) 再试 "cats" 递归 dfs(4)，dfs(4) 试 "and" 又要 dfs(7)，这次 memo[7] 已缓存直接返回，拼成 "and dog"，dfs(0) 收到 "cats and dog"。最终返回这两句。

复杂度为什么甩不掉「输出量」，['']和[]差一个空串却天差地别

每个起点算一次，但内层枚举右端 j、每次要构造并哈希子串 s[i..j)，构造就耗 O(j−i)，枚举加构造升到 O(n³)；句子可能指数级多，整体 O(n³ + 输出量)。空间是递归深度 O(n) 加 memo。

整串本身是词时 dfs 返回它这一句；拼不通那层返回 []，dfs(0) 得空列表；单字符同理。最阴的是拿 [''] 当失败：它是拼满整串的成功信号，误当空列表，句子会在最后一层被丢光。