139. 单词拆分

项目	内容
链接	LeetCode CN
标签	动态规划 · 字符串 · 哈希
源码	`0139-word-break.py`

一、题目理解

题意

给定字符串 s 和字典 wordDict，判断能否把 s 完全拆成字典中的单词（单词可重复使用）。

示例

s = "leetcode"
wordDict = ["leet", "code"]
→ True   "leet" + "code"

s = "applepenapple"
wordDict = ["apple", "pen"]
→ True   "apple" + "pen" + "apple"

s = "catsandog"
wordDict = ["cats","dog","sand","and","cat"]
→ False  无法无剩余字符地拼完

DP 状态定义

dp[i]：前 i 个字符 s[0:i] 能否被拆分（i 从 0 到 n）。

dp[0] = True（空串合法）
目标：dp[n]

二、思路总览

flowchart TD
    A["dp[0] = True"] --> B["for i in 0..n-1"]
    B --> C["枚举 wordDict 中每个 word"]
    C --> D{"s[i-len+1:i+1] == word 且 dp[i-len+1]?"}
    D -->|是| E["dp[i+1] = True, break"]
    D -->|否| C
    E --> B
    B --> F["return dp[n]"]

步骤	做什么
1	初始化 `dp[0] = True`
2	对每个结束位置 `i+1`，尝试用某个 word 作为最后一段
3	若前缀可拆且后缀匹配 word → `dp[i+1] = True`

三、解法演进

方法一：一维 DP 枚举词表

转移：以位置 i+1 为结尾，若存在 word 满足：

len(word) <= i+1
s[i+1-len : i+1] == word
dp[i+1-len] == True

则 dp[i+1] = True。

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(n):
        for word in wordDict:
            m = len(word)
            if m - 1 > i:
                continue
            if word == s[i + 1 - m: i + 1] and dp[i - m + 1]:
                dp[i + 1] = True
                break
    return dp[-1]

索引说明：循环变量 i 是「当前考察的最后一个字符下标」；dp[i+1] 表示前 i+1 个字符。

方法二：DP + 哈希优化词查找

将 wordDict 转为 set，内层改为枚举切分点 j：

for i in range(1, n + 1):
    for j in range(i):
        if dp[j] and s[j:i] in word_set:
            dp[i] = True
            break

切分点枚举 O(n²)，适合词表很大、单词很长的场景对比。

四、实现代码

from typing import List


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        for i in range(n):
            for word in wordDict:
                m = len(word)
                if m - 1 > i:
                    continue
                if word == s[i + 1 - m: i + 1] and dp[i - m + 1]:
                    dp[i + 1] = True
                    break
        return dp[-1]

五、复杂度

指标	值
时间	O(n × m × L)，n=
空间	O(n)

注意：

dp 长度 n+1，答案在 dp[n] 即 dp[-1]
单词可重复使用：同一 word 可多次匹配

相关：140 单词拆分 II 需回溯输出所有方案，不止判布尔。

FilesExpand file tree

0139-word-break.md

Latest commit

History