单词拆分 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) 得空列表；单字符同理。最阴的是拿 [''] 当失败：它是拼满整串的成功信号，误当空列表，句子会在最后一层被丢光。

Python

from typing import List
from functools import lru_cache
class 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)

C++

#include <functional>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> words(wordDict.begin(), wordDict.end());
        unordered_map<int, vector<string>> memo;
        function<vector<string>(int)> dfs = [&](int i) -> vector<string> {
            if (memo.count(i)) return memo[i];
            if (i == (int)s.size()) return vector<string>{""};
            vector<string> ans;
            for (int j = i + 1; j <= (int)s.size(); ++j) {
                string word = s.substr(i, j - i);
                if (words.count(word)) for (auto tail : dfs(j)) ans.push_back(tail.empty() ? word : word + " " + tail);
            }
            return memo[i] = ans;
        };
        return dfs(0);
    }
};

Java

import java.util.*;
class Solution {
    Set<String> words;
    Map<Integer, List<String>> memo;
    String s;
    public List<String> wordBreak(String s, List<String> wordDict) {
        this.s = s; words = new HashSet<>(wordDict); memo = new HashMap<>();
        return dfs(0);
    }
    private List<String> dfs(int i) {
        if (memo.containsKey(i)) return memo.get(i);
        if (i == s.length()) return new ArrayList<>(Arrays.asList(""));
        List<String> ans = new ArrayList<>();
        for (int j = i + 1; j <= s.length(); j++) {
            String word = s.substring(i, j);
            if (words.contains(word)) for (String tail : dfs(j)) ans.add(tail.isEmpty() ? word : word + " " + tail);
        }
        memo.put(i, ans);
        return ans;
    }
}