139. 单词拆分

题目链接（中等）

题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

数据范围：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s 和 wordDict[i] 仅由小写英文字母组成
• wordDict 中的所有字符串 互不相同

示例

示例 1：

输入： s = "leetcode", wordDict = ["leet", "code"]
输出： true
解释： 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入： s = "applepenapple", wordDict = ["apple", "pen"]
输出： true
解释： 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意，你可以重复使用字典中的单词。

示例 3：

输入： s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出： false

方法一：动态规划

思路及解法

定义 dp[i] 表示字符串 s 的前 i 个字符 s[0..i-1] 能否被字典中的单词拼接出来。

转移思路：枚举最后一个单词的起点 j（0 <= j < i），把 s[0..i-1] 切成两部分：

• 前一部分 s[0..j-1]：是否合法由 dp[j] 表示；
• 后一部分 s[j..i-1]：检查它是否在字典中。

只要存在一个 j 使得两者都成立，dp[i] 就是 True：

$$dp[i] = \bigvee_{0 \le j < i} \left( dp[j] \ \text{且}\ s[j..i-1] \in \text{wordDict} \right)$$

边界条件：dp[0] = True，表示空串合法（作为递归的起点）。

哈希集合：把 wordDict 转成 set，判断子串是否在字典中是 $O(1)$。

直觉理解：把字符串从左往右切，每切一刀判断「前面部分能不能拆分」+「后面这一刀切出的单词在不在字典里」。只要找到一个合法的切法，当前位置就可行。

代码

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        word_set = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True

        for i in range(1, n + 1):
            for j in range(i):
                # 前 j 个字符可拆分，且 s[j:i] 在字典里
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break

        return dp[n]

复杂度分析

• 时间复杂度：$O(n^2)$，共 $n$ 个状态，每个状态枚举 $O(n)$ 个分割点，子串哈希判断 $O(1)$（但 s[j:i] 切片本身需要 $O(k)$，本题长度小可忽略）。
• 空间复杂度：$O(n)$，dp 数组 + 哈希集合。

方法二：动态规划 + 剪枝（按单词长度倒序枚举）

思路及解法

方法一每次枚举所有分割点，其实可以剪枝：最后一个单词的长度不可能超过字典中最长单词的长度。

因此枚举 j 时，可以从 i - 1 往前推，一旦 i - j > max_len 就停止。

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        word_set = set(wordDict)
        max_len = max(len(w) for w in wordDict)
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True

        for i in range(1, n + 1):
            # 从后往前枚举 j，一旦长度超过 max_len 就停
            for j in range(i - 1, max(i - max_len - 1, -1), -1):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break

        return dp[n]

复杂度分析

• 时间复杂度：$O(n \cdot L)$，其中 $L$ 是字典中最长单词的长度，内层最多枚举 $L$ 次。
• 空间复杂度：$O(n)$。

方法三：记忆化搜索（自顶向下）

思路及解法

从 s 的某个位置 start 出发，尝试用字典中每个单词去匹配，如果匹配成功就递归到下一个位置，直到到达字符串末尾。

用 memo 缓存已经计算过的 start，避免重复搜索。

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        word_set = set(wordDict)
        memo = {}

        def dfs(start: int) -> bool:
            if start == len(s):
                return True
            if start in memo:
                return memo[start]

            for end in range(start + 1, len(s) + 1):
                if s[start:end] in word_set and dfs(end):
                    memo[start] = True
                    return True

            memo[start] = False
            return False

        return dfs(0)

也可以让 dfs 枚举字典里的每个单词去尝试匹配，思路一样。

复杂度分析

• 时间复杂度：$O(n^2)$，共 $n$ 个状态，每个状态最多尝试 $O(n)$ 个子串。
• 空间复杂度：$O(n)$，memo 字典和递归栈。

三种方法对比

方法	时间	空间	特点
DP（正序枚举 j）	$O(n^2)$	$O(n)$	最标准，最直观
DP + 剪枝	$O(n \cdot L)$	$O(n)$	利用最长单词长度优化
记忆化搜索	$O(n^2)$	$O(n)$	自顶向下，代码自然

推荐：

• 面试：方法一（标准 DP），思路清晰，容易讲；
• 加分：方法二（加剪枝），展示优化意识；
• 偏好递归：方法三（记忆化搜索），和回溯/DFS 的思维更接近。

总结

• 状态定义：dp[i] = s 前 i 个字符能否被字典拆分；
• 转移方程：dp[i] = any(dp[j] and s[j:i] in wordSet)，其中 0 <= j < i；
• 边界条件：dp[0] = True（空串合法）；
• 哈希集合：把「单词是否在字典中」的判断降到 $O(1)$；
• 优化方向：倒序枚举 j，一旦 i - j > max_len 就 break；
• 类似的思路：把「字符串切割」问题转化为「前缀是否可达」，是字符串 DP 的经典套路。