网站开发公司起名字,珠海网站友情链接,网站开发目前主要用什么技术,做网站程序的步骤文章目录 前言摘要描述题解答案题解代码题解代码分析示例测试及结果时间复杂度空间复杂度总结 前言 本题由于没有合适答案为以往遗留问题#xff0c;最近有时间将以往遗留问题一一完善。 LeetCode - #140 单词拆分 II 不积跬步#xff0c;无以至千里#xff1b;不积小流最近有时间将以往遗留问题一一完善。 LeetCode - #140 单词拆分 II 不积跬步无以至千里不积小流无以成江海Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言我们会尽力满足大家的需求。 难度水平困难 摘要
本篇文章将探讨如何在 Swift 中解决字符串分割问题即将给定字符串根据字典中的单词构造出所有可能的句子。本问题属于经典的递归与动态规划问题涉及搜索和记忆化优化。我们将通过详细的代码示例和分析为您展现解决该问题的完整流程。
描述
给定一个字符串 s 和一个字符串列表 wordDict作为字典我们需要将字符串 s 划分为多个子串使每个子串均在 wordDict 中并返回所有可能的句子。
字典中的单词可以重复使用。如果无法划分返回空数组。 题解答案
本题可以通过 递归 记忆化 解决。我们使用递归的方式遍历所有可能的分割点并将中间结果缓存以避免重复计算。
核心思路
遍历字符串的前缀部分检查它是否在字典中。如果是则递归处理剩余部分。将递归结果与当前前缀拼接成完整的句子。利用字典存储每个子问题的结果避免重复计算。
题解代码
以下是实现代码
import Foundationfunc 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] sentencesreturn sentences}return dfs(s)
}题解代码分析 字典转集合 将 wordDict 转换为 Set可以将单词查找时间从 O(k) 降低到 O(1)其中 k 是字典中单词的数量。 记忆化搜索 利用 memo 缓存每个子问题的结果避免重复计算。递归中每次处理一个子串时先检查是否已计算过结果。 递归分割字符串 遍历字符串的所有分割点将字符串划分为前缀和后缀。如果前缀在字典中则递归处理后缀。最终将前缀和后缀的结果拼接成句子。 拼接结果 对于每种可能的分割将前缀与后缀的句子组合成完整句子。返回所有可能的句子。
示例测试及结果
示例 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。代码清晰易懂性能也相对优秀。对于字符串分割、组合类问题这是一种经典且高效的解决方法。
希望通过本篇文章您能够更好地理解递归和记忆化搜索的应用
