题目链接 · 灵神原题解（署名来源）

题意

把 $s$ 划分成若干段，使得每段都在 $\mathit{\text{wordDict}}$ 中。

判断能否划分。

注意可以不划分，如果 $s$ 在 $\mathit{\text{wordDict}}$ 中，则返回 $\mathtt{\text{true}}$。

一、寻找子问题

例如 $s=\mathtt{\text{leetcode}}$，枚举最后一段的长度：

• 长为 $1$，即子串 $\mathtt{\text{e}}$，如果它在 $\mathit{\text{wordDict}}$ 中，那么问题变成：能否把 $\mathtt{\text{leetcod}}$ 划分成若干段，使得每段都在 $\mathit{\text{wordDict}}$ 中？
• 长为 $2$，即子串 $\mathtt{\text{de}}$，如果它在 $\mathit{\text{wordDict}}$ 中，那么问题变成：能否把 $\mathtt{\text{leetco}}$ 划分成若干段，使得每段都在 $\mathit{\text{wordDict}}$ 中？
• 长为 $3$，即子串 $\mathtt{\text{ode}}$，如果它在 $\mathit{\text{wordDict}}$ 中，那么问题变成：能否把 $\mathtt{\text{leetc}}$ 划分成若干段，使得每段都在 $\mathit{\text{wordDict}}$ 中？
• 长为 $4$，即子串 $\mathtt{\text{code}}$，如果它在 $\mathit{\text{wordDict}}$ 中，那么问题变成：能否把 $\mathtt{\text{leet}}$ 划分成若干段，使得每段都在 $\mathit{\text{wordDict}}$ 中？
• ……

这些问题都是和原问题相似的、规模更小的子问题，可以用递归解决。

⚠注意：本题 $\mathit{\text{wordDict}}$ 至多有 $1000$ 个字符串，但最多只有 $20$ 种不同的长度，所以应该枚举长度，而不是枚举 $\mathit{\text{wordDict}}$ 中的字符串。

注：从右往左思考，主要是为了方便把递归翻译成递推。从左往右思考也是可以的。

二、状态定义与状态转移方程

根据上面的讨论，定义状态为 $\mathit{\text{dfs}}(i)$，表示能否把前缀 $s[:i]$（表示 $s[0]$ 到 $s[i-1]$ 这段子串）划分成若干段，使得每段都在 $\mathit{\text{wordDict}}$ 中。

枚举 $s[:i]$ 最后一段的长度：

• 长为 $1$，即子串 $s[i-1:i]$，如果它在 $\mathit{\text{wordDict}}$ 中，那么问题变成：能否把前缀 $s[:i-1]$ 划分成若干段，使得每段都在 $\mathit{\text{wordDict}}$ 中，即 $\mathit{\text{dfs}}(i-1)$。
• 长为 $2$，即子串 $s[i-2:i]$，如果它在 $\mathit{\text{wordDict}}$ 中，那么问题变成：能否把前缀 $s[:i-2]$ 划分成若干段，使得每段都在 $\mathit{\text{wordDict}}$ 中，即 $\mathit{\text{dfs}}(i-2)$。
• 长为 $3$，即子串 $s[i-3:i]$，如果它在 $\mathit{\text{wordDict}}$ 中，那么问题变成：能否把前缀 $s[:i-3]$ 划分成若干段，使得每段都在 $\mathit{\text{wordDict}}$ 中，即 $\mathit{\text{dfs}}(i-3)$。
• ……

设 $\mathit{\text{wordDict}}$ 中字符串的最长长度为 $\mathit{\text{maxLen}}$，枚举的上限不超过 $\mathit{\text{maxLen}}$，因为更长的子串必然不在 $\mathit{\text{wordDict}}$ 中。

枚举 $j=i-1,i-2,i-3,\dots ,max(i-\mathit{\text{maxLen}},0)$，只要其中一个 $j$ 满足 $s[j:i]$ 在 $\mathit{\text{wordDict}}$ 中且 $\mathit{\text{dfs}}(j)=\mathtt{\text{true}}$，那么 $\mathit{\text{dfs}}(i)$ 就是 $\mathtt{\text{true}}$。

用数学记号表示，就是

$$\mathit{\text{dfs}}(i)=\underset{\begin{array}{c}max(i-\mathit{\text{maxLen}},0)\le j<i\\ s[j:i]\in \mathit{\text{wordDict}}\end{array}}{\bigvee }\mathit{\text{dfs}}(j)$$

递归边界：$\mathit{\text{dfs}}(0)=\mathtt{\text{true}}$。递归到空串，说明 $s$ 成功地划分完毕。

递归入口：$\mathit{\text{dfs}}(n)$，也就是答案。

代码实现时，可以把 $\mathit{\text{wordDict}}$ 列表转成一个哈希集合，便于快速判断子串是否在 $\mathit{\text{wordDict}}$ 中。

三、递归搜索 + 保存递归返回值 = 记忆化搜索

考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：

• 如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 $\mathit{\text{memo}}$ 数组中。
• 如果一个状态不是第一次遇到（$\mathit{\text{memo}}$ 中保存的结果不等于 $\mathit{\text{memo}}$ 的初始值），那么可以直接返回 $\mathit{\text{memo}}$ 中保存的结果。

注意：$\mathit{\text{memo}}$ 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 $0$（表示 $\mathtt{\text{false}}$），并且要记忆化的 $\mathit{\text{dfs}}(i)$ 也等于 $0$（表示 $\mathtt{\text{false}}$），那就没法判断 $0$ 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 $-1$。

Python 用户可以无视上面这段，直接用 @cache 装饰器。

具体请看视频讲解 动态规划入门：从记忆化搜索到递推，其中包含把记忆化搜索 1:1 翻译成递推的技巧。

Python 解法1

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        max_len = max(map(len, wordDict))  # 用于限制下面 j 的循环次数
        words = set(wordDict)  # 便于快速判断 s[j:i] in words

        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int) -> bool:
            if i == 0:  # 成功拆分！
                return True
            for j in range(i - 1, max(i - max_len - 1, -1), -1):
                if s[j:i] in words and dfs(j):
                    return True
            return False

        return dfs(len(s))

C++ 解法1

// C++ 版待补充

Python 解法2

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        max_len = max(map(len, wordDict))  # 用于限制下面 j 的循环次数
        words = set(wordDict)  # 便于快速判断 s[j:i] in words

        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int) -> bool:
            if i == 0:  # 成功拆分！
                return True
            return any(s[j:i] in words and dfs(j)
                       for j in range(i - 1, max(i - max_len - 1, -1), -1))

        return dfs(len(s))

C++ 解法2

// C++ 版待补充

C++ 解法3

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int max_len = ranges::max(wordDict, {}, &string::size).size();
        unordered_set<string> words(wordDict.begin(), wordDict.end());

        int n = s.size();
        vector<int> memo(n + 1, -1); // -1 表示没有计算过

        auto dfs = [&](this auto&& dfs, int i) -> bool {
            if (i == 0) { // 成功拆分！
                return true;
            }
            int& res = memo[i]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            for (int j = i - 1; j >= max(i - max_len, 0); j--) {
                if (words.contains(s.substr(j, i - j)) && dfs(j)) {
                    return res = true; // 记忆化
                }
            }
            return res = false; // 记忆化
        };

        return dfs(n);
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(mL+n{L}^2)$，其中 $m$ 是 $\mathit{\text{wordDict}}$ 的长度，$L\le 20$ 是 $\mathit{\text{wordDict}}$ 中字符串的最长长度，$n$ 是 $s$ 的长度。创建哈希集合需要 $\mathcal{O}(mL)$ 的时间。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(n)$，单个状态的计算时间为 $\mathcal{O}(L^2)$（注意判断子串是否在哈希集合中需要 $\mathcal{O}(L)$ 的时间），所以记忆化搜索的时间复杂度为 $\mathcal{O}(n{L}^2)$。
• 空间复杂度：$\mathcal{O}(mL+n)$。哈希集合需要 $\mathcal{O}(mL)$ 的空间。记忆化搜索需要 $\mathcal{O}(n)$ 的空间。

四、1:1 翻译成递推

我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。

具体来说，$f[i]$ 的定义和 $\mathit{\text{dfs}}(i)$ 的定义是一样的，都表示能否把前缀 $s[:i]$（表示 $s[0]$ 到 $s[i-1]$）划分成若干段，使得每段都在 $\mathit{\text{wordDict}}$ 中。

同样地，枚举 $j=i-1,i-2,i-3,\dots ,max(i-\mathit{\text{maxLen}},0)$，只要其中一个 $j$ 满足 $s[j:i]$ 在 $\mathit{\text{wordDict}}$ 中且 $f[j]=\mathtt{\text{true}}$，那么 $f[i]$ 就是 $\mathtt{\text{true}}$。

用数学记号表示，就是

$$f[i]=\underset{\begin{array}{c}max(i-\mathit{\text{maxLen}},0)\le j<i\\ s[j:i]\in \mathit{\text{wordDict}}\end{array}}{\bigvee }f[j]$$

初始值 $f[0]=\mathtt{\text{true}}$，翻译自递归边界 $\mathit{\text{dfs}}(0)=\mathtt{\text{true}}$。

答案为 $f[n]$，翻译自递归入口 $\mathit{\text{dfs}}(n)$。

答疑

问：能不能外层循环枚举 $\mathit{\text{words}}$，内层循环枚举长度？类似完全背包的写法。

答：不能。完全背包是同一个物品连续选择，然后就再也不选这个物品了。本题可以交替选。比如 $s$ 是 ABA 型，如果用完全背包的写法，只能枚举 AAB、ABB 这类连续的字符串组合，无法枚举到 ABA 这样的字符串组合。

Python 解法4

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        max_len = max(map(len, wordDict))  # 用于限制下面 j 的循环次数
        words = set(wordDict)  # 便于快速判断 s[j:i] in words

        n = len(s)
        f = [True] + [False] * n
        for i in range(1, n + 1):
            for j in range(i - 1, max(i - max_len - 1, -1), -1):
                if f[j] and s[j:i] in words:
                    f[i] = True
                    break
        return f[n]

C++ 解法4

// C++ 版待补充

Python 解法5

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        max_len = max(map(len, wordDict))  # 用于限制下面 j 的循环次数
        words = set(wordDict)  # 便于快速判断 s[j:i] in words

        n = len(s)
        f = [True] + [False] * n
        for i in range(1, n + 1):
            f[i] = any(f[j] and s[j:i] in words
                       for j in range(i - 1, max(i - max_len - 1, -1), -1))
        return f[n]

C++ 解法5

// C++ 版待补充

C++ 解法6

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int max_len = ranges::max(wordDict, {}, &string::size).size();
        unordered_set<string> words(wordDict.begin(), wordDict.end());

        int n = s.size();
        vector<int> f(n + 1);
        f[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i - 1; j >= max(i - max_len, 0); j--) {
                if (f[j] && words.contains(s.substr(j, i - j))) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[n];
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(mL+n{L}^2)$，其中 $m$ 是 $\mathit{\text{wordDict}}$ 的长度，$L\le 20$ 是 $\mathit{\text{wordDict}}$ 中字符串的最长长度，$n$ 是 $s$ 的长度。理由同上。
• 空间复杂度：$\mathcal{O}(mL+n)$。

注：本题字符串比较短，可以直接用哈希集合判断。如果字符串比较长，可以用字典树优化到 $\mathcal{O}(mL+nL)$ 时间复杂度。

专题训练

见下面动态规划题单的「五、划分型 DP」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府