单词拆分
Word Break
本机进度仅保存在当前浏览器
题目描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格分割为一个或多个在字典中出现的单词（字典单词可重复使用）。
示例：s = "leetcode"，wordDict = ["leet", "code"]，输出 true。
解题思路
- 状态 dp[i]：s 的前 i 个字符能否被字典拆分；dp[0] = true 表示空串可拆。
- 转移：枚举最后一个单词 s[j..i)，dp[i] = exists j 使 dp[j] 且 s[j:i] 在字典中。
- 字典用哈希集合保证 O(1) 查询；枚举上限可设为字典最长单词长度，避免无效长度的子串查询。
参考实现
查看参考实现Python · 建议先自行作答
def wordBreak(s, wordDict):
words = set(wordDict)
max_len = max(map(len, words))
dp = [True] + [False] * len(s)
for i in range(1, len(s) + 1):
# 枚举最后一个单词的起点
for j in range(max(0, i - max_len), i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[len(s)]