江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第139题：单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

题目描述

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

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

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 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

提示

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅有小写英文字母组成
  • wordDict 中的所有字符串 互不相同

解题思路

方法一：动态规划

这道题要求判断字符串s是否可以被拆分成字典中的单词。我们可以使用动态规划来解决这个问题。

关键点：

  • 定义dp[i]表示字符串s的前i个字符是否可以被拆分成字典中的单词
  • 如果dp[j]为true且s[j…i-1]在字典中，则dp[i]为true
  • 初始状态：dp[0] = true，表示空字符串可以被拆分

具体步骤：

  1. 创建一个长度为n+1的布尔数组dp，其中n是字符串s的长度
  2. 初始化dp[0] = true，表示空字符串可以被拆分
  3. 遍历字符串s的每个位置i（从1到n）：
    • 遍历所有可能的拆分点j（从0到i-1）：
      • 如果dp[j]为true且s[j…i-1]在字典中，则dp[i] = true
  4. 返回dp[n]

时间复杂度：O(n²)，其中n是字符串s的长度。需要遍历所有可能的拆分点。 空间复杂度：O(n)，需要一个长度为n+1的数组存储中间结果。

方法二：记忆化搜索

我们也可以使用记忆化搜索（自顶向下的动态规划）来解决这个问题。

关键点：

  • 使用递归函数检查字符串s[start…end]是否可以被拆分
  • 使用记忆数组避免重复计算
  • 如果s[start…i-1]在字典中且s[i…end]可以被拆分，则s[start…end]可以被拆分

具体步骤：

  1. 创建一个记忆数组memo，用于存储中间结果
  2. 定义递归函数canBreak(s, start)，表示字符串s[start…end]是否可以被拆分
  3. 如果start等于s的长度，返回true（空字符串可以被拆分）
  4. 如果memo[start]已经计算过，直接返回结果
  5. 遍历所有可能的拆分点i（从start+1到s的长度）：
    • 如果s[start…i-1]在字典中且canBreak(s, i)为true，则返回true
  6. 将结果存入memo[start]并返回

时间复杂度：O(n²)，其中n是字符串s的长度。每个子问题只会计算一次。 空间复杂度：O(n)，需要一个长度为n的数组存储中间结果，以及递归调用栈的空间。

图解思路

动态规划分析表

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

i s[0…i-1] dp[i] 计算过程 说明
0 “” true 初始状态 空字符串可以被拆分
1 “l” false “l”不在字典中 无法拆分
2 “le” false “le”不在字典中，“e”不在字典中 无法拆分
3 “lee” false “lee”不在字典中，“ee”不在字典中，“e”不在字典中 无法拆分
4 “leet” true dp[0] = true且“leet”在字典中 可以拆分为“leet”
5 “leetc” false 无法拆分 无法拆分
6 “leetco” false 无法拆分 无法拆分
7 “leetcod” false 无法拆分 无法拆分
8 “leetcode” true dp[4] = true且“code”在字典中 可以拆分为“leet”+“code”

记忆化搜索分析表

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

调用 参数 结果 计算过程 说明
canBreak start = 0 true 检查s[0…]是否可以被拆分 主函数调用
canBreak start = 4 true 检查s[4…]是否可以被拆分 “leet”在字典中，检查剩余部分
canBreak start = 8 true 检查s[8…]是否可以被拆分 到达字符串末尾，返回true
canBreak start = 0 true “leet”在字典中且canBreak(4) = true 返回true

代码实现

C# 实现

public class Solution {
    public bool WordBreak(string s, IList<string> wordDict) {
        int n = s.Length;
        bool[] dp = new bool[n + 1];
        dp[0] = true;
        
        // 将字典转换为HashSet，提高查找效率
        HashSet<string> wordSet = new HashSet<string>(wordDict);
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.Contains(s.Substring(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
}

Python 实现

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        
        # 将字典转换为集合，提高查找效率
        word_set = set(wordDict)
        
        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break
        
        return dp[n]

C++ 实现

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.length();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        
        // 将字典转换为unordered_set，提高查找效率
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
};

执行结果

C# 实现

  • 执行用时：88 ms
  • 内存消耗：39.8 MB

Python 实现

  • 执行用时：36 ms
  • 内存消耗：16.3 MB

C++ 实现

  • 执行用时：4 ms
  • 内存消耗：7.6 MB

性能对比

语言 执行用时 内存消耗 特点
C# 88 ms 39.8 MB 执行速度适中，内存消耗较高
Python 36 ms 16.3 MB 执行速度适中，内存消耗适中
C++ 4 ms 7.6 MB 执行速度最快，内存消耗最低

代码亮点

  1. 🎯 使用动态规划解决问题，时间复杂度为O(n²)
  2. 💡 将字典转换为哈希集合，提高查找效率
  3. 🔍 使用布尔数组存储中间结果，节省空间
  4. 🎨 代码结构简洁，逻辑清晰易懂

常见错误分析

  1. 🚫 没有正确初始化dp[0] = true，导致无法正确处理边界情况
  2. 🚫 使用暴力递归而不是动态规划，导致超时
  3. 🚫 没有使用哈希集合存储字典，导致查找效率低下
  4. 🚫 字符串截取操作不正确，导致结果错误

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
动态规划 O(n²) O(n) 实现简单，思路清晰 时间复杂度较高
记忆化搜索 O(n²) O(n) 代码简洁，易于理解 递归调用可能导致栈溢出
BFS O(n²) O(n) 避免递归调用 实现稍复杂

相关题目