当前位置：首页 > news >正文

LeetCode 139. Word Break 题解

news 2026/5/12 20:31:40

LeetCode 139. Word Break 题解

题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

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

示例 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 个字符是否可以被拆分成字典中的单词

状态转移方程：

dp[i] = True，如果存在 j < i，使得 dp[j] = True 且 s[j:i] 在字典中

初始条件：

dp[0] = True（空字符串可以被拆分）

代码实现

方法一：动态规划

def wordBreak(s, wordDict): word_set = set(wordDict) n = len(s) # dp[i] 表示前 i 个字符是否可以被拆分 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]

方法二：优化内层循环

def wordBreak(s, wordDict): word_set = set(wordDict) n = len(s) # 找到字典中最长单词的长度 max_len = max(len(word) for word in wordDict) if wordDict else 0 dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): # 只需要检查长度不超过 max_len 的子串 for j in range(max(0, i - max_len), i): if dp[j] and s[j:i] in word_set: dp[i] = True break return dp[n]

复杂度分析

时间复杂度：O(n² × m)，其中 n 是字符串长度，m 是字典中最长单词的长度
空间复杂度：O(n)，dp 数组的空间

BFS 解法

也可以使用 BFS 解决：

from collections import deque def wordBreak(s, wordDict): word_set = set(wordDict) n = len(s) visited = [False] * n queue = deque([0]) while queue: start = queue.popleft() if visited[start]: continue visited[start] = True for end in range(start + 1, n + 1): if s[start:end] in word_set: if end == n: return True queue.append(end) return False

测试案例

# 测试案例 1 assert wordBreak("leetcode", ["leet", "code"]) == True # 测试案例 2 assert wordBreak("applepenapple", ["apple", "pen"]) == True # 测试案例 3 assert wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]) == False # 测试案例 4 assert wordBreak("", ["a"]) == True # 测试案例 5 assert wordBreak("a", []) == False