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总结本题是动态规划的经典应用也是字符串拆分问题的基础。关键点状态定义dp[i] 表示前 i 个字符是否可以被拆分状态转移枚举所有可能的拆分点优化限制内层循环的范围通过本题可以深入理解动态规划在字符串问题中的应用。