动态规划与BFS解决字符串分割问题：从LeetCode 139讲起-北京尧图网络

最近在刷算法题时遇到一类“字符串分割”问题题目描述常常是“给定一个字符串和一个单词字典判断该字符串是否能被分割成字典中的单词”。很多朋友一看就觉得是简单的子串匹配上手就写暴力搜索结果在稍长的字符串面前直接超时。这就像《卖瓜》名场面里的那句“这瓜保熟吗”——你以为只是简单的一刀切但真要高效、准确地“切分”这个字符串背后考验的是对动态规划、哈希表、搜索剪枝等核心算法的深刻理解。暴力切法回溯在数据量面前不堪一击而高效的动态规划解法才是那个“一刀下去瓜熟蒂落”的利刃。本文要解决的就是“字符串分割”这类问题的通解。我们将从一个具体的LeetCode真题139. 单词拆分入手彻底讲清楚为什么暴力回溯会超时时间复杂度是指数级的字符串一长就“爆炸”。动态规划DP如何优雅解决将大问题分解为子问题时间复杂度降至 O(n²)。如何用记忆化搜索优化回溯结合递归的直观与DP的效率。BFS视角的独特解法将问题转化为图论中的路径寻找。工程实践中的陷阱与最佳实践如何处理空串、空字典、超大输入等边界情况。读完本文你不仅能轻松解决LeetCode 139更能掌握一套应对“字符串能否被某种规则分割/覆盖/匹配”这类问题的通用方法论。下次再遇到“有一个字符串前来买瓜”你就能稳、准、狠地给出最优解。1. 问题定义与核心难点为什么“切瓜”不简单我们先明确问题。以 LeetCode 139. 单词拆分为例题目描述给定一个非空字符串s和一个包含非空单词列表的字典wordDict判定s是否可以被空格分割为一个或多个在字典中出现的单词。注意字典中的单词可以重复使用且不要求全部使用。示例输入: s leetcode, wordDict [leet, code] 输出: true 解释: leetcode 可以被分割为 leet code。输入: s applepenapple, wordDict [apple, pen] 输出: true 解释: applepenapple 可以被分割为 apple pen apple。输入: s catsandog, wordDict [cats, dog, sand, and, cat] 输出: false第一直觉与陷阱很多人的第一反应是遍历字符串从开头找只要当前子串在字典里就切一刀然后从下一个位置继续。这本质上是贪心思想。但看第三个例子s catsandog,wordDict [cats, dog, sand, and, cat]从开头找到cat在字典里切一刀剩下sandog。从sandog开头找到sand在字典里切一刀剩下og。og不在字典里贪心失败返回false。但实际上存在一种分割catsandog不og不在字典里。实际上正确的分割是catsandog不对仔细看og确实不在字典。那是不是无解题目给的输出就是false。贪心在这里碰巧得到了正确结果但它是不稳定的。考虑这个例子s aaaaaaa,wordDict [aaaa, aaa]贪心从开头匹配先匹配aaaa剩下aaa可以匹配成功。但如果字典是[aaa, aaaa]贪心先匹配aaa剩下aaaa也可以匹配也成功。这个例子贪心都能成功但如果我们改一下s aaaaaaa,wordDict [aaaa, aa]。贪心先匹配aaaa剩下aaaaaa不能被[aa]完全分割因为aaa分成aa和aa不在字典贪心失败。但实际上存在分割aaaaaaa不a不在字典。等一下aaaaaaa是7个a用aa分会剩下一个a。所以其实无解让我们用程序验证。实际上aa可以分3次覆盖6个a剩下1个a无法覆盖。所以确实无解。贪心失败的结果false是正确的。但贪心算法本身无法保证总是正确因为它做了局部最优选择匹配最长的或第一个找到的单词而忽略了后续状态可能因为这次选择而被堵死。真正的核心难点在于在某个位置i切一刀即s[0:i]是一个单词剩下的部分s[i:]必须也能被完全分割。这形成了一个重叠子问题判断s[i:]能否被分割和判断整个s能否被分割是同一类问题且规模更小。这正是动态规划的典型特征。因此我们不能只凭“第一刀”的感觉必须系统地考察所有可能的分割点。这就是为什么我们需要更强大的算法。2. 基础概念与解法思想在深入代码前我们先统一几个关键概念和解题的核心思想。2.1 状态定义动态规划的核心是定义状态。对于字符串s长度为n。我们定义dp[i]表示字符串s的前i个字符即s[0:i]能否被字典wordDict完全分割。注意dp[i]对应的是s的子串s[0:i]长度为i。dp[0]表示空串的状态。2.2 状态转移方程如何求得dp[i]呢我们需要枚举最后一个单词的结束位置i并尝试所有可能的分割点j0 j i。如果dp[j]为true即前缀s[0:j]可以被分割。并且子串s[j:i]即从j到i-1的字符存在于字典wordDict中。那么整个前缀s[0:i]就可以通过s[0:j]可分割加上s[j:i]一个字典单词的方式完成分割。因此dp[i] true。状态转移方程可以表示为dp[i] true如果存在某个j (0 j i)使得dp[j] true且s[j:i] in wordDict。否则dp[i] false。2.3 初始状态dp[0]表示空串能否被分割。空串通常被认为是可以被分割的即不需要任何单词就能构成因为它对应于我们分割的起点。所以dp[0] true。2.4 最终答案我们要求的是整个字符串s能否被分割即s[0:n]的状态也就是dp[n]的值。2.5 字典的优化查找在状态转移中我们需要频繁判断子串s[j:i]是否在字典中。如果每次都用list的in操作O(m)m为字典大小总时间复杂度会很高。更高效的做法是将wordDict转换为集合set这样in操作的平均时间复杂度是 O(1)。3. 环境准备与前置条件为了运行后续的代码示例你需要准备一个 Python 3.6 的环境。本文的所有代码都将使用 Python 实现因为其语法简洁易于理解算法本质。你也可以用 Java、C 等语言实现核心逻辑完全一致。所需环境Python 3.6 或更高版本一个代码编辑器或 IDE如 VS Code, PyCharm无需安装额外第三方库关键前置知识基本的 Python 语法字符串切片、列表、集合动态规划的基本思想对递归和广度优先搜索BFS有初步了解更佳4. 核心解法一动态规划标准解法这是最经典、最高效的解法。我们按照上述思想实现。from typing import List class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: 动态规划解法 :param s: 待分割字符串 :param wordDict: 单词字典列表 :return: 布尔值表示s能否被分割 n len(s) # 将字典列表转为集合加速查找 word_set set(wordDict) # dp数组初始化dp[i]表示s的前i个字符能否被分割 dp [False] * (n 1) # 空串可以被分割 dp[0] True # 填充dp数组i代表当前子串的结束位置长度 for i in range(1, n 1): # 枚举所有可能的分割点j for j in range(i): # 如果s[0:j]可分割且s[j:i]在字典中则s[0:i]可分割 if dp[j] and s[j:i] in word_set: dp[i] True # 一旦找到一种分割方式就可以跳出内层循环 break return dp[n] # 测试代码 if __name__ __main__: solution Solution() # 测试用例1 s1 leetcode wordDict1 [leet, code] print(f测试 {s1}: {solution.wordBreak(s1, wordDict1)}) # 应输出 True # 测试用例2 s2 applepenapple wordDict2 [apple, pen] print(f测试 {s2}: {solution.wordBreak(s2, wordDict2)}) # 应输出 True # 测试用例3 s3 catsandog wordDict3 [cats, dog, sand, and, cat] print(f测试 {s3}: {solution.wordBreak(s3, wordDict3)}) # 应输出 False # 测试用例4贪心可能出错的例子 s4 aaaaaaa wordDict4 [aaaa, aa] print(f测试 {s4}: {solution.wordBreak(s4, wordDict4)}) # 应输出 False代码逻辑详解初始化n是字符串长度。word_set是字典集合用于 O(1) 查找。dp数组长度为n1dp[0]True。双重循环外层循环i从 1 到 n代表当前考虑的子串s[0:i]的长度。内层循环j从 0 到 i-1代表可能的分割点。j将子串s[0:i]分为s[0:j]和s[j:i]两部分。状态转移对于每个j检查dp[j]是否为真前半部分可分割且s[j:i]是否在字典中后半部分是一个完整单词。如果两者都满足则dp[i]为真并可以提前结束内层循环因为已经找到一种分割方式。返回结果最终dp[n]就是整个字符串s的可分割性。时间复杂度O(n²)其中 n 是字符串长度。因为有两层循环且字符串切片s[j:i]操作在 Python 中平均是 O(k)k为子串长度但整体仍可视为 O(n²) 级别。使用集合查找是 O(1)。空间复杂度O(n) 用于 dp 数组O(m) 用于存储单词集合m为字典单词总字符数通常远小于n²的影响。5. 核心解法二记忆化回溯递归备忘录动态规划是自底向上的迭代而记忆化搜索是自顶向下的递归但通过“备忘录”避免重复计算效率等价于动态规划。这种写法更符合直觉从字符串开头尝试匹配如果匹配到一个单词就递归判断剩下的部分。from typing import List from functools import lru_cache class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: 记忆化回溯解法使用lru_cache装饰器实现备忘录 word_set set(wordDict) lru_cache(maxsizeNone) # 无限大小的缓存避免重复计算 def can_break(start: int) - bool: 判断子串 s[start:] 能否被分割 :param start: 当前起始索引 :return: 布尔值 # 递归终止条件如果起始位置已经到达字符串末尾说明之前的分割都成功了 if start len(s): return True # 尝试所有可能的结束位置 for end in range(start 1, len(s) 1): # 如果当前切片是一个单词并且剩余部分也能被分割 if s[start:end] in word_set and can_break(end): return True # 所有尝试都失败 return False return can_break(0) # 测试代码同上可复用 if __name__ __main__: solution Solution() s catsanddog # 这个可以被分割 cats and dog wordDict [cats, dog, sand, and, cat] print(f记忆化回溯测试 {s}: {solution.wordBreak(s, wordDict)}) # 应输出 True代码逻辑详解递归函数can_break(start)判断从索引start开始的子串能否被分割。终止条件如果start len(s)说明已经成功走到了字符串末尾返回True。递归过程从start开始尝试所有可能的结束位置end。如果子串s[start:end]在字典中就递归判断can_break(end)。记忆化lru_cache装饰器自动缓存函数调用的结果。当用相同的参数start再次调用时直接返回缓存的结果避免了指数级的重复递归。返回如果找到任何一种分割方式使得递归链最终返回True则整个函数返回True。优点思路直观代码简洁。lru_cache让记忆化实现变得极其容易。缺点递归深度受字符串长度限制对于极长的字符串可能有栈溢出风险尽管Python递归深度默认约1000且本题一般不会达到。逻辑上它和动态规划是等价的。6. 核心解法三广度优先搜索BFS我们可以将这个问题转化为一个图论问题将字符串的每个位置看作图中的节点。如果子串s[i:j]在字典中那么就存在一条从节点i到节点j的边。问题就变成了是否存在一条从节点0到节点n的路径。BFS 非常适合寻找最短路径或判断连通性。from typing import List from collections import deque class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: 广度优先搜索BFS解法 word_set set(wordDict) n len(s) # visited 数组用于标记位置是否被访问过避免重复入队 visited [False] * (n 1) visited[0] True # 起始位置 queue deque([0]) # 队列中存储的是起始索引 while queue: start queue.popleft() # 尝试从当前start位置扩展到所有可能的end位置 for end in range(start 1, n 1): # 如果end位置未被访问过且s[start:end]是一个单词 if not visited[end] and s[start:end] in word_set: # 如果已经到达字符串末尾成功 if end n: return True # 否则将end作为新的起点加入队列 queue.append(end) visited[end] True return False # 测试代码 if __name__ __main__: solution Solution() test_cases [ (leetcode, [leet, code], True), (applepenapple, [apple, pen], True), (catsandog, [cats, dog, sand, and, cat], False), (aaaaaaa, [aaaa, aa], False), ] for s, wordDict, expected in test_cases: result solution.wordBreak(s, wordDict) print(fBFS测试 {s}: {result} (期望: {expected}))代码逻辑详解初始化visited数组标记每个索引位置是否被访问过。队列queue存储待处理的起始索引初始为0。BFS循环当队列不为空时取出一个起始索引start。扩展对于这个start枚举所有可能的结束索引end。如果s[start:end]是一个单词且end位置未被访问过则如果end n说明已经到达字符串末尾找到了一条完整路径返回True。否则将end标记为已访问并加入队列作为下一轮 BFS 的起点。结束如果 BFS 结束都没有找到到达n的路径返回False。为什么需要visited数组如果不记录访问状态同一个位置可能被多次加入队列导致时间复杂度急剧上升甚至无限循环。例如字符串aaaa字典[a]从位置0可以到1从1可以到2...但如果不标记从位置0到1后位置1处理时又会尝试到2但位置0也可能通过其他路径再次尝试到1造成重复。时间复杂度最坏情况 O(n²)和动态规划类似。每个节点最多入队一次每次出队需要 O(n) 时间尝试所有结束位置。空间复杂度O(n) 用于队列和 visited 数组。7. 运行结果与效果验证将上述三种解法的代码分别保存为dp_solution.py、memo_solution.py、bfs_solution.py运行后应得到一致的正确结果。预期输出示例测试 leetcode: True 测试 applepenapple: True 测试 catsandog: False 测试 aaaaaaa: False 记忆化回溯测试 catsanddog: True BFS测试 leetcode: True (期望: True) BFS测试 applepenapple: True (期望: True) BFS测试 catsandog: False (期望: False) BFS测试 aaaaaaa: False (期望: False)如何验证算法正确性使用LeetCode平台将代码提交到 LeetCode 139 题通过所有测试用例是最直接的验证。设计边界测试空字符串s ,wordDict [a]应返回True空串可分割LeetCode规定s非空但我们的代码dp[0]True是合理的逻辑基础。字典为空s a,wordDict []应返回False。字典包含空字符串理论上字典单词非空但若输入包含我们的集合会包含可能导致错误匹配。实际题目约束了单词非空但健壮的代码可以考虑过滤掉空字符串。字符串极长用重复模式测试例如s a * 1000,wordDict [a]应快速返回True。如果使用无记忆化的回溯会超时而DP/BFS/记忆化搜索应能快速处理。性能对比对于长度150左右的字符串三种解法都应能在毫秒级完成。可以导入time模块简单计时。8. 常见问题与排查思路在实际编码和调试中你可能会遇到以下问题问题现象可能原因排查方式解决方案动态规划解法返回错误答案如应为True却返回False1.dp[0]未初始化为True。2. 内层循环j的范围错误如for j in range(i)写成了for j in range(1, i)。3. 字符串切片索引错误s[j:i]是左闭右开对应从j到i-1的字符。1. 打印dp数组中间状态观察dp[0]和每一步的更新。2. 使用简单的测试用例如sa,wordDict[a]手动推导dp数组应为[True, True]。1. 确保dp[0] True。2. 检查循环边界j应从0开始。3. 理解Python切片语义s[start:end]不包含end。记忆化回溯超时Time Limit Exceeded未使用记忆化或记忆化未生效。递归树呈指数级膨胀。1. 检查是否使用了lru_cache或手动备忘录。2. 打印递归调用次数如果随字符串长度增长极快说明记忆化失效。1. 确保装饰器正确应用函数参数是可哈希的如int。2. 如果手动实现备忘录确保在返回前存储结果并在递归开始检查是否已计算。BFS解法陷入死循环或超时未使用visited数组标记已访问节点导致同一节点反复入队。打印队列大小和visited数组观察是否有节点被重复访问。在将节点加入队列前标记其为已访问 (visited[node] True)。所有解法都对但某个特定用例错误字典单词有重复或包含空字符串影响了集合查找或逻辑判断。打印word_set检查其内容。添加输入验证。在创建word_set前可以过滤掉空字符串word_set set(word for word in wordDict if word)。对于超长字符串如长度10^4内存溢出或超时1. DP解法中内层循环的优化不足。2. 字典单词长度可能很长但字符串切片操作成本高。1. 分析最坏时间复杂度 O(n²) 是否可接受。对于10^4n²10^8在Python中可能处于临界。2. 考虑优化只枚举可能的单词长度而非所有j。优化策略先获取字典中单词的最大长度max_len。在内层循环中j从max(0, i - max_len)开始枚举因为单词长度不会超过max_len。这可以将内层循环从 O(n) 降到 O(max_len)。9. 最佳实践与工程建议掌握了基础解法后我们来看看如何写出更健壮、更高效的代码以及如何应对实际场景中的挑战。9.1 算法选择建议面试或竞赛首选动态规划。它思路经典代码规整能体现算法功底且效率稳定。快速实现或原型记忆化回溯使用lru_cache代码最简洁直观不易出错。需要求最短分割次数等变体问题BFS天然适合求解最短路径可以很容易地修改为记录路径或步数。9.2 性能优化技巧字典预处理始终将wordDict转换为set进行 O(1) 查找。限制枚举范围DP优化class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: word_set set(wordDict) max_len max((len(word) for word in wordDict), default0) n len(s) dp [False] * (n 1) dp[0] True for i in range(1, n 1): # j 只需要从 i - max_len 开始枚举但不能小于0 start max(0, i - max_len) for j in range(start, i): if dp[j] and s[j:i] in word_set: dp[i] True break return dp[n]这个优化在字典单词平均长度远小于字符串长度时效果显著。提前剪枝在 BFS 或回溯中如果发现某个位置start出发所有可能的单词长度都无法匹配可以提前记录该位置为“死胡同”避免后续重复尝试这需要额外的失败记忆数组类似于记忆化。9.3 边界条件与鲁棒性输入验证虽然题目有约束但生产代码应考虑if not s: # 根据题意s非空但可做防御 return False if not wordDict: return False word_set set(word for word in wordDict if word) # 过滤空字符串超大字典如果wordDict非常大如10^5个单词将其全部存入set可能内存压力大。可以考虑使用Trie前缀树来存储字典并在 DP 过程中进行匹配。这样可以在匹配时提前失败如果前缀不存在但实现更复杂。9.4 变体问题拓展掌握基础问题后可以尝试解决变体巩固理解140. 单词拆分 II要求返回所有可能的分割句子。这需要结合 DP判断可行性和回溯收集路径。139 的变体求最少分割次数将dp[i]定义为使s[0:i]可分割的最少单词数。状态转移方程变为dp[i] min(dp[j] 1)其中j i且s[j:i] in word_set且dp[j] ! INF。判断是否可以用字典构造出整个字符串单词可重复使用这就是本题本身。判断是否可以用字典构造出整个字符串单词最多使用一次这变成了一个背包问题需要记录单词的使用状态复杂度更高。9.5 调试与日志在开发过程中添加简单的日志有助于理解算法流程def wordBreak_debug(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): if dp[j] and s[j:i] in word_set: print(fdp[{i}] True, because dp[{j}] is True and s[{j}:{i}]{s[j:i]} in dict) dp[i] True break print(fdp array after i{i}: {dp}) return dp[n]10. 总结与核心思维提炼“字符串分割”问题是一个经典的动态规划入门题但它巧妙地串联了多个核心算法思想。回顾整个探索过程我们可以提炼出以下核心思维模式它们能帮助你解决一大类字符串处理与状态决策问题从暴力到优化最直接的思路是回溯枚举所有分割点。当发现存在大量重复子问题如判断s[i:]多次时立刻想到记忆化搜索或动态规划。这是优化递归问题的标准路径。状态定义的艺术DP 的关键在于如何定义子问题。本题定义dp[i]为“前 i 个字符能否分割”是一个布尔值。对于变体问题如求最少分割数状态值可能就是整数。定义的状态要能表征子问题的解并能通过更小的子问题推导出来。转化视角将字符串分割视为图论中的路径问题BFS解法展示了算法之间的连通性。这种多角度思考的能力能让你在面试中脱颖而出。预处理是朋友将列表转换为集合进行 O(1) 查找是一个简单却极其有效的优化。在字符串问题中预处理字典构建 Trie、计算最大最小长度也是常见技巧。边界与效率时刻考虑最坏情况。对于长度为 n 的字符串O(n²) 的 DP 解法在 n 较大时如 10^4可能勉强通过需要进一步优化如限制单词最大长度。理解算法复杂度的来源才能有针对性地优化。回到开头的比喻“有一个字符串前来买瓜”你现在已经掌握了不止一把刀动态规划是一把经过精密计算的手术刀规划好每一刀的位置稳扎稳打。记忆化回溯是一把智能刻刀跟着感觉走但会记住走过的路避免重复雕刻。广度优先搜索是一把探路刀系统地探索所有可能的切割路径直到找到出口。下次再遇到类似的“分割”、“覆盖”、“匹配”问题不妨先问自己是否存在重叠子问题能否定义状态能否构建状态转移方程这套思维框架远比记住一道题的代码更有价值。建议将本文的三种解法代码收藏并尝试用它们去解决 LeetCode 140单词拆分 II亲自体验一下从“判断是否”到“找出所有”的思维跃迁。字符串的世界里精准的“切割”从来不只是体力活更是算法思想的体现。

动态规划与BFS解决字符串分割问题：从LeetCode 139讲起

相关推荐

YOLOv5工业火焰识别实战：从数据采集到边缘部署

华为OD机试真题新系统 2026-08-16 C++【智能家居模式调度优化】

【计算机工具类-CI和CD工具Skills】azure-functions 技能

更多资讯

《AI 推文三天百万播放 0-1 分享》

【AI职场提效系列 01】职场邮件不用愁，AI 3分钟搞定高质量草稿

Behringer 推 300 美元开源 DJ 一体机，四通道价格砍到对手零头

笔记++24

笔记++25

写入用 ZSet，读取当 List？拆解一套真实零售 SaaS 的促销缓存翻车记

今日更新

GUI自动化测试中的ScreenLayout：从硬编码坐标到声明式画面地图

LLC谐振变换器12V25A 300W开关电源设计与调试全攻略

ESP32多应用Flash数据隔离：分区表与NVS namespace实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

相关推荐

YOLOv5工业火焰识别实战：从数据采集到边缘部署

华为OD机试真题 新系统 2026-08-16 C++【智能家居模式调度优化】

【计算机工具类-CI和CD工具Skills】azure-functions 技能

更多资讯

《AI 推文三天百万播放 0-1 分享》

【AI职场提效系列 01】职场邮件不用愁，AI 3分钟搞定高质量草稿

Behringer 推 300 美元开源 DJ 一体机，四通道价格砍到对手零头

笔记++24

笔记++25

写入用 ZSet，读取当 List？拆解一套真实零售 SaaS 的促销缓存翻车记

今日更新

GUI自动化测试中的ScreenLayout：从硬编码坐标到声明式画面地图

LLC谐振变换器12V25A 300W开关电源设计与调试全攻略

ESP32多应用Flash数据隔离：分区表与NVS namespace实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

华为OD机试真题新系统 2026-08-16 C++【智能家居模式调度优化】