LeetCode - #139 单词拆分

前言

本题由于没有合适答案为以往遗留问题，最近有时间将以往遗留问题一一完善。

我们社区陆续会将顾毅（Netflix 增长黑客，《iOS 面试之道》作者，ACE 职业健身教练。）的 Swift 算法题题解整理为文字版以方便大家学习与阅读。

不积跬步，无以至千里；不积小流，无以成江海，Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：中等

摘要

1. 描述

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

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

2. 示例

示例 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 中的所有字符串 互不相同

3. 答案

题解

我们可以使用动态规划（Dynamic Programming, DP）来解决该问题。

动态规划的思路

1. 定义状态:

   • 用一个布尔数组 dp 表示字符串的可拼接状态。
   • dp[i] 表示字符串 s[0..<i] 是否可以由字典中的单词拼接而成。

2. 状态转移方程:

   • 如果存在一个 j，使得 dp[j] == true 且 s[j..<i] 是字典中的一个单词，则 dp[i] = true。
   • 换句话说，dp[i] 取决于之前某个位置 j 的状态和当前子字符串是否在字典中。

3. 初始化:

   • dp[0] = true，表示空字符串可以被拼接。

4. 结果:

   • 最终答案是 dp[s.count]。

代码实现

func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
    // 将 wordDict 转换为 Set，方便快速查询单词是否存在
    let wordSet = Set(wordDict)
    let n = s.count
    // 初始化 DP 数组，默认值为 false
    var dp = Array(repeating: false, count: n + 1)
    dp[0] = true // 空字符串可以被拼接

    // 将字符串转换为字符数组，便于索引操作
    let sArray = Array(s)

    // 遍历字符串长度
    for i in 1...n {
        // 检查所有可能的子字符串
        for j in 0..<i {
            // 子字符串 s[j..<i]
            let substring = String(sArray[j..<i])
            if dp[j] && wordSet.contains(substring) {
                dp[i] = true
                break
            }
        }
    }
    return dp[n]
}

代码解析

1. 将 wordDict 转换为 Set

let wordSet = Set(wordDict)

将字典转换为 Set，可以将查找时间从 O(k) 降低到 O(1)，其中 k 是字典中单词的个数。

2. 初始化 DP 数组

var dp = Array(repeating: false, count: n + 1)
dp[0] = true

• dp[i] 的值表示从字符串的起始到第 i 个字符（不含 i）的子字符串是否可以拼接。
• 初始状态 dp[0] = true 表示空字符串总是可以拼接。

3. 状态转移方程

for i in 1...n {
    for j in 0..<i {
        let substring = String(sArray[j..<i])
        if dp[j] && wordSet.contains(substring) {
            dp[i] = true
            break
        }
    }
}

• 对于每个位置 i，检查从 j 到 i 的子字符串 s[j..<i] 是否存在于字典中。
• 如果存在，并且 dp[j] == true，说明从 0..<j 的部分可以拼接，则更新 dp[i] = true。

4. 返回结果

return dp[n]

dp[n] 表示整个字符串是否可以拼接。

测试用例

示例 1:

let s = "leetcode"
let wordDict = ["leet", "code"]
print(wordBreak(s, wordDict)) // 输出: true

解释: s 可以拆分为 “leet” 和 “code”，两者都在字典中。

示例 2:

let s = "applepenapple"
let wordDict = ["apple", "pen"]
print(wordBreak(s, wordDict)) // 输出: true

解释: s 可以拆分为 “apple”、“pen” 和 “apple”，所有单词都在字典中。

示例 3:

let s = "catsandog"
let wordDict = ["cats", "dog", "sand", "and", "cat"]
print(wordBreak(s, wordDict)) // 输出: false

解释: 无法将 s 拆分成字典中的单词组合。

时间复杂度

1. 外层循环:
   • 遍历字符串长度 n。
2. 内层循环:
   • 遍历每个子字符串 j 到 i，最多运行 n 次。
3. 子字符串查找:
   • 查找操作在字典中为 O(1)。

总时间复杂度为 O(n²)。

空间复杂度

• DP 数组占用 O(n)。
• 转换的 wordSet 占用 O(k)，其中 k 是字典中单词的个数。

总空间复杂度为 O(n + k)。

总结

• 本题通过动态规划的方法，利用子问题的结果推导出整体结果，避免了重复计算。
• 关键在于正确理解状态转移方程，以及将问题分解为可复用的子问题。
• 代码简洁，适合处理字符串拼接类问题。

关于我们

我们是由 Swift 爱好者共同维护，我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容，也整理收集优秀的学习资料。