当前位置: 首页 > news >正文

上海的外贸网站建设公司营销团队找产品合作

上海的外贸网站建设公司,营销团队找产品合作,淘宝宝贝链接怎么做相关网站,建立网站的详细步骤文章目录 前言摘要描述题解答案题解代码题解代码分析示例测试及结果时间复杂度空间复杂度总结 前言 本题由于没有合适答案为以往遗留问题,最近有时间将以往遗留问题一一完善。 LeetCode - #140 单词拆分 II 不积跬步,无以至千里;不积小流&…

在这里插入图片描述
在这里插入图片描述

文章目录

    • 前言
    • 摘要
    • 描述
    • 题解答案
    • 题解代码
    • 题解代码分析
    • 示例测试及结果
    • 时间复杂度
    • 空间复杂度
    • 总结

前言

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

LeetCode - #140 单词拆分 II

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

难度水平:困难

摘要

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

描述

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

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

题解答案

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

核心思路:

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

题解代码

以下是实现代码:

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

题解代码分析

  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)。代码清晰易懂,性能也相对优秀。对于字符串分割、组合类问题,这是一种经典且高效的解决方法。

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

http://www.mmbaike.com/news/35481.html

相关文章:

  • google seo 营销网站制作网站的软件
  • 新余哪有做网站的公司第一设计
  • 免费新闻网站建设黄冈网站推广软件费用是多少
  • 电商网站定制网店推广方法有哪些
  • 郑州设计公司招聘自动seo系统
  • 网站方案范文南京百度推广优化排名
  • dnf怎么做钓鱼网站关键词点击工具
  • wordpress站长seo标题优化裤子关键词
  • 国内做免费视频网站搜索引擎营销的基本方法
  • 张店区创业孵化中心有做网站的吗镇江百度推广
  • 专门做干果批发的网站hao123网址之家官网
  • 巴士定制网站开发青岛关键词搜索排名
  • wordpress 手机端 广告关键词排名优化易下拉软件
  • 能够做渗透的网站长沙网站seo外包
  • 公司网站建设申请报告怎么制作一个自己的网站
  • 做网站怎么导入地图电脑软件推广平台
  • 东莞网站设计定制开发站长素材音效
  • 怎么打开文件做的网站网络营销师主要做什么
  • 设计个网站需要怎么做福州seo服务
  • 武汉网站设计招聘百度账号安全中心
  • 用别人身份证备案网站seo基础
  • 企业品牌战略新网站应该怎么做seo
  • 做策划有帮助的网站网络优化软件
  • 枣庄网站制作百度seo优化是什么
  • 网站名查询seo自学网视频教程
  • 上海免费网站建站模板百度客户端电脑版下载
  • 孝感网站推广郑州网站建设价格
  • 南昌哪里有网站建设网站设计的基本原则
  • html简单的旅游网页seo优化推广技巧
  • ui设计网站模板推广有什么好方法