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

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)
}

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

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

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