在 Swift 中实现字符串分割问题：以字典中的单词构造句子

前言

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

LeetCode - #140 单词拆分 II

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

难度水平：困难

摘要

本篇文章将探讨如何在 Swift 中解决字符串分割问题，即将给定字符串根据字典中的单词构造出所有可能的句子。本问题属于经典的递归与动态规划问题，涉及搜索和记忆化优化。我们将通过详细的代码示例和分析，为您展现解决该问题的完整流程。

描述

给定一个字符串 s 和一个字符串列表 wordDict（作为字典），我们需要将字符串 s 划分为多个子串，使每个子串均在 wordDict 中，并返回所有可能的句子。

• 字典中的单词可以重复使用。
• 如果无法划分，返回空数组。

题解答案

本题可以通过 递归 + 记忆化 解决。我们使用递归的方式遍历所有可能的分割点，并将中间结果缓存以避免重复计算。

核心思路：

1. 遍历字符串的前缀部分，检查它是否在字典中。
2. 如果是，则递归处理剩余部分。
3. 将递归结果与当前前缀拼接成完整的句子。
4. 利用字典存储每个子问题的结果，避免重复计算。

题解代码

以下是实现代码：

import Foundation

func wordBreak(_ s: String, _ wordDict: [String]) -> [String] {
    // 将字典转换为 Set 提高查询速度
    let wordSet = Set(wordDict)
    // 用于存储子问题的解，避免重复计算
    var memo = [String: [String]]()
    
    func dfs(_ s: String) -> [String] {
        // 如果子问题已计算过，直接返回结果
        if let result = memo[s] {
            return result
        }
        
        var sentences = [String]()
        // 如果字符串本身是一个单词，直接加入结果
        if wordSet.contains(s) {
            sentences.append(s)
        }
        
        // 遍历字符串的每个位置，将其分割为前缀和后缀
        for i in 1..<s.count {
            let prefix = String(s.prefix(i))
            if wordSet.contains(prefix) {
                let suffix = String(s.suffix(s.count - i))
                // 递归处理后缀部分
                let suffixSentences = dfs(suffix)
                // 将当前前缀与后缀的句子拼接
                for sentence in suffixSentences {
                    sentences.append(prefix + " " + sentence)
                }
            }
        }
        // 缓存当前字符串的结果
        memo[s] = sentences
        return sentences
    }
    
    return dfs(s)
}

题解代码分析

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

2. 记忆化搜索
   利用 memo 缓存每个子问题的结果，避免重复计算。递归中每次处理一个子串时，先检查是否已计算过结果。

3. 递归分割字符串

   • 遍历字符串的所有分割点，将字符串划分为前缀和后缀。
   • 如果前缀在字典中，则递归处理后缀。
   • 最终将前缀和后缀的结果拼接成句子。

4. 拼接结果

   • 对于每种可能的分割，将前缀与后缀的句子组合成完整句子。
   • 返回所有可能的句子。

示例测试及结果

示例 1:

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

示例 2:

let s = "pineapplepenapple"
let wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
print(wordBreak(s, wordDict))
// 输出: ["pine apple pen apple", "pineapple pen apple", "pine applepen apple"]

示例 3:

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

时间复杂度

• 递归部分: 假设字符串长度为 n，字典中单词数量为 k。每次递归处理子串，并尝试所有分割点，最坏情况下复杂度为 O(2^n)。
• 优化部分: 由于使用记忆化缓存了中间结果，实际复杂度降低到 O(n * k)，其中 n 是字符串长度，k 是字典中单词的数量。

空间复杂度

• 递归栈空间: 最深递归深度为字符串长度 n，栈空间复杂度为 O(n)。
• 缓存空间: 需要存储所有子问题的结果，空间复杂度为 O(n * m)，其中 m 是平均句子数量。

总结

通过递归 + 记忆化的方式，我们可以高效地解决字符串分割问题。本方法利用了动态规划的思想，避免了重复计算，适用于字符串长度较小的情况（如本题中的限制 s.length <= 20）。代码清晰易懂，性能也相对优秀。对于字符串分割、组合类问题，这是一种经典且高效的解决方法。

希望通过本篇文章，您能够更好地理解递归和记忆化搜索的应用！