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

代码随想录算法训练营第45天 | 115.不同的子序列、583. 两个字符串的删除操作、72. 编辑距离

115.不同的子序列

题目链接:. - 力扣(LeetCode)

func numDistinct(s string, t string) int {dp:=make([][]int,len(s)+1)arr:=make([]int,len(t)+1)arr[0]=1for i:=range dp{dp[i]=append([]int{},arr...)}//dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。for i:=1;i<len(dp);i++{for j:=1;j<len(dp[i]);j++{if s[i-1]==t[j-1]{dp[i][j]=dp[i-1][j-1]+dp[i-1][j]}else{dp[i][j]=dp[i-1][j]}}}return dp[len(s)][len(t)]
}

583. 两个字符串的删除操作

题目链接:. - 力扣(LeetCode)

func minDistance(word1 string, word2 string) int {dp:=make([][]int,len(word1)+1)arr:=make([]int,len(word2)+1)for i:=range dp{dp[i]=append([]int{},arr...)}for i:=range dp[0]{dp[0][i]=i}for i:=range dp{dp[i][0]=i}// dp[i][j]: word1 i,word2 j 所需的最小步数for i:=1;i<len(dp);i++{for j:=1;j<len(dp[i]);j++{if word1[i-1]==word2[j-1]{dp[i][j]=dp[i-1][j-1]}else{dp[i][j]=min(dp[i-1][j-1]+1,min(dp[i][j-1],dp[i-1][j]))+1}}}return dp[len(word1)][len(word2)]
}

72. 编辑距离

题目链接:. - 力扣(LeetCode)

func minDistance(word1 string, word2 string) int {dp:=make([][]int,len(word1)+1)arr:=make([]int,len(word2)+1)for i:=range dp{dp[i]=append([]int{},arr...)}for i:=range dp[0]{dp[0][i]=i}for i:=range dp{dp[i][0]=i}// dp[i][j]: word1 i,word2 j 所需的最小步数for i:=1;i<len(dp);i++{for j:=1;j<len(dp[i]);j++{if word1[i-1]==word2[j-1]{dp[i][j]=dp[i-1][j-1]}else{dp[i][j]=min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1}}}return dp[len(word1)][len(word2)]
}


http://www.mrgr.cn/news/75233.html

相关文章:

  • PyQt5 详细安装与配置教程及使用
  • 数字后端教程之Innovus report_property和get_property使用方法及应用案例
  • 【MySQL】explain之type类型
  • MFC图形函数学习08——绘图函数的重载介绍
  • 在CentOS下安装RabbitMQ
  • 苍穹外卖 数据可视化
  • python os.path.join 详解
  • mysql锁机制详解
  • 刀客doc:《再见爱人4》能带动芒果TV的广告营收吗?
  • 【学习日记】notebook添加JAVA支持
  • Android Framework AMS(17)APP 异常Crash处理流程解读
  • 教你使用 Lisp 编写 ChatGPT 对话机器人
  • 解决 Mybatis-Plus 中 `updateById` 方法不更新空值、更新字段无效的问题
  • Altium Designer使用技巧(五)
  • 微服务day08
  • AUTOSAR_EXP_ARAComAPI的7章笔记(3)
  • 17-鸿蒙开发中的背景图片设置:位置、定位、单位和尺寸
  • Linux软件包管理与Vim编辑器使用指南
  • 绝对路径和相对路径的区别
  • 搜维尔科技:我们使用Xsens动作捕捉技术创建的短片
  • 行驶证 OCR 识别 API 接口的优势分析
  • Python中,处理日期和时间的库
  • GCN基于图卷积神经网络多特征分类预测(多输入单输出) Matlab代码
  • springboot039基于Web足球青训俱乐部管理系统
  • 似然函数解析
  • LeetCode 每日一题 统计满足 K 约束的子字符串数量 I