LeetCode 139. 单词拆分 - 动态规划解法详解

LeetCode 139. 单词拆分 - 动态规划解法详解

题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

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

示例

• 示例1：s = “leetcode”, wordDict = [“leet”, “code”] → true
• 示例2：s = “applepenapple”, wordDict = [“apple”, “pen”] → true
• 示例3：s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] → false

最推荐解决方案：动态规划

核心思想

使用动态规划思想，定义 dp[i] 表示字符串 s 的前 i 个字符是否可以被字典中的单词拼接而成。

关键变量说明

1. dp[i]：布尔数组，表示字符串 s 的前 i 个字符是否可以拆分

   • dp[0] = true：空字符串可以被拆分（边界条件）
   • dp[i] = true：表示 s[0…i-1] 可以被字典单词拼接

2. wordSet：将字典转换为HashSet，提高查找效率（O(1)时间复杂度）

3. 状态转移方程：

   dp[i] = dp[j] && wordSet.contains(s.substring(j, i))
   

   其中 j 是所有可能的分割点 (0 ≤ j < i)

Java代码实现

import java.util.*;public class Solution {public boolean wordBreak(String s, List<String> wordDict) {// 将字典转换为HashSet，提高查找效率Set<String> wordSet = new HashSet<>(wordDict);// dp[i]表示字符串s的前i个字符是否可以拆分boolean[] dp = new boolean[s.length() + 1];// 边界条件：空字符串可以拆分dp[0] = true;// 遍历字符串的每个位置for (int i = 1; i <= s.length(); i++) {// 尝试所有可能的分割点jfor (int j = 0; j < i; j++) {// 如果前j个字符可以拆分，且j到i的子串在字典中if (dp[j] && wordSet.contains(s.substring(j, i))) {dp[i] = true;break; // 找到一种拆分方式即可}}}return dp[s.length()];}
}

算法可视化演示

以示例1为例：s = “leetcode”, wordDict = [“leet”, “code”]

初始状态

字符串: l e e t c o d e
索引:   0 1 2 3 4 5 6 7 8
dp数组: T F F F F F F F F↑dp[0]=true (边界条件)

执行过程详解

i=1 时 (检查 “l”)

检查分割点 j=0:
- dp[0] = true ✓
- s.substring(0,1) = "l" ∉ wordSet ✗
- dp[1] = falsedp数组: T F F F F F F F F

i=2 时 (检查 “le”)

检查分割点 j=0:
- dp[0] = true ✓
- s.substring(0,2) = "le" ∉ wordSet ✗检查分割点 j=1:
- dp[1] = false ✗dp数组: T F F F F F F F F

i=3 时 (检查 “lee”)

检查分割点 j=0:
- dp[0] = true ✓
- s.substring(0,3) = "lee" ∉ wordSet ✗检查分割点 j=1:
- dp[1] = false ✗检查分割点 j=2:
- dp[2] = false ✗dp数组: T F F F F F F F F

i=4 时 (检查 “leet”) 🔥关键步骤

检查分割点 j=0:
- dp[0] = true ✓
- s.substring(0,4) = "leet" ∈ wordSet ✓
- dp[4] = true，跳出内循环dp数组: T F F F T F F F F↑找到第一个可拆分点

i=5 时 (检查 “leetc”)

检查分割点 j=0:
- dp[0] = true ✓
- s.substring(0,5) = "leetc" ∉ wordSet ✗检查分割点 j=1-3:
- dp[1-3] = false ✗检查分割点 j=4:
- dp[4] = true ✓
- s.substring(4,5) = "c" ∉ wordSet ✗dp数组: T F F F T F F F F

i=6 时 (检查 “leetco”)

类似过程，所有分割方式都失败
dp数组: T F F F T F F F F

i=7 时 (检查 “leetcod”)

类似过程，所有分割方式都失败
dp数组: T F F F T F F F F

i=8 时 (检查 “leetcode”) 🔥关键步骤

检查分割点 j=0-3:
- 各种组合都失败检查分割点 j=4:
- dp[4] = true ✓
- s.substring(4,8) = "code" ∈ wordSet ✓
- dp[8] = true，跳出内循环dp数组: T F F F T F F F T↑最终结果：可拆分

最终状态图

字符串: l e e t | c o d e
分割:     leet  |  code
dp数组: T F F F T F F F T
对应:   空 l le lee leet leetc leetco leetcod leetcode

复杂度分析

• 时间复杂度：O(n² × m)

  • n 是字符串长度
  • m 是字典中最长单词的长度（substring操作）
  • 外层循环 O(n)，内层循环 O(n)，substring 操作 O(m)

• 空间复杂度：O(n + k)

  • dp数组：O(n)
  • HashSet存储字典：O(k)，k为字典中所有单词的总长度

代码分支覆盖测试

测试用例1：可以完全拆分

s = "leetcode", wordDict = ["leet", "code"]
预期结果: true
覆盖分支: dp[j] && wordSet.contains() 都为true的情况

测试用例2：无法拆分

s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
预期结果: false
覆盖分支: 所有分割尝试都失败的情况

测试用例3：需要重复使用单词

s = "applepenapple", wordDict = ["apple", "pen"]
预期结果: true
覆盖分支: 字典单词可重复使用的情况

关键优化点

1. 使用HashSet：将List转换为HashSet，查找时间从O(k)降到O(1)
2. 提前跳出：找到一种可行拆分就break，避免不必要的计算
3. 边界处理：dp[0]=true作为递推基础

总结

动态规划解法是单词拆分问题的最优解，具有以下优势：

• 思路清晰：状态定义直观，转移方程简单
• 效率较高：避免了递归的重复计算
• 易于理解：自底向上的计算过程符合直觉