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

❤️独特的算法❤️:一文解决编辑距离问题

编辑距离问题

题目关键点
115. 不同的子序列 - 力扣(LeetCode)*dp数组定义,情况讨论
583. 两个字符串的删除操作 - 力扣(LeetCode)两个字符串删除,情况讨论多加一种
72. 编辑距离 - 力扣(LeetCode)删除 == 添加 、替换操作?
  • 115. 不同的子序列 - 力扣(LeetCode)

    1. 确定dp数组(dp table)以及下标的含义

      dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数dp[i][j]

      这样定义,注定s中要删除元素,满足t的条件。比如s:bagg,t:bag,那么就需要s中删除元素满足t的条件。

    本题刚开始的dp数组定义就与之前子序列的定义不同,所以分析方法也不同。

    1. 确定递推公式:这一类问题,基本是要分析两种情况

      • s[i - 1] 与 t[j - 1]相等时,dp[i][j]可以有两部分组成。

        • 一部分是用s[i - 1]来匹配,那么个数不变,还是看上一个序列的个数dp[i - 1][j - 1]。-
        • 一部分是不用s[i - 1]来匹配,个数为dp[i - 1][j]。因为s序列中可能出现重复的部分。

        例如: s:bagg 和 t:bag ,s[3] 和 t[2]是相同的,但是字符串s也可以不用s[3]来匹配,即用s[0]s[1]s[2]组成的bag。当然也可以用s[3]来匹配,即:s[0]s[1]s[3]组成的bag。

      • s[i - 1] 与 t[j - 1] 不相等

        • dp[i][j]只有一部分组成,不用s[i - 1]来匹配(就是模拟在s中删除这个元素),即:dp[i - 1][j]

        所以递推公式为:dp[i][j] = dp[i - 1][j];

  1. dp数组如何初始化

    从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j] 是从上方和左上方推导而来,那么dp[i][0]dp[0][j]是一定要初始化的。

    • dp[i][0] 表示:以i-1为结尾的s可以随便删除元素,出现空字符串的个数。那么dp[i][0]一定都是1,因为把以i-1为结尾的s,删除所有元素,出现空字符串的个数就是1。

    • dp[0][j]:空字符串s可以随便删除元素,出现以j-1为结尾的字符串t的个数。那么dp[0][j]一定都是0,s如论如何也变成不了t。

    • dp[0][0]应该是1,空字符串s,可以删除0个元素,变成空字符串t。

  2. 遍历的时候一定是从上到下,从左到右,这样保证dp[i][j]可以根据之前计算出来的数值进行计算。

    class Solution {public int numDistinct(String s, String t) {int m = s.length();int n = t.length();int [][] dp = new int [m + 1][n + 1];//dp数组的初始化for(int i = 1 ; i <= m ; i ++){dp[i][0] = 1;}for(int i = 1 ; i <= n ; i ++){dp[0][i] = 0;}dp[0][0] = 1;for(int i = 1 ; i <= m ; i ++){char s1 = s.charAt(i - 1);for(int j = 1 ; j <= n ; j ++){char t1 = t.charAt(j - 1);//s1 == t1 存在两种情况,不用s[i - 1]匹配 + 用s[i - 1]匹配if(s1 == t1) dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];//s1 != t1 只有一种情况,不用s[i - 1]匹配。else dp[i][j] = dp[i - 1][j];// System.out.println("以s[" + (i - 1) + "]结尾的字符串中,以t[" + (j - 1) +"]结尾的子序列的个数为" + dp[i][j]);}}return dp[m][n];}
    }
    
  • 583. 两个字符串的删除操作 - 力扣(LeetCode)

    1. dp定义:dp[i][j]:以i - 1结尾的word1和以j - 1结尾的word2,删除字符后使两个单词相等的最小删除步数为dp[i][j]

    2. dp数组推导:

      word1[i - 1] = word2[j - 1]:不需要删除:dp[i][j] = dp[i - 1][j - 1]

      word1[i - 1] != word2[j - 1]:需要删除:删除word1或删除word2dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)

      dp[i - 1][j],此时dp数组的定义为以i - 2结尾的word1和以j - 1结尾的word2,删除字符后使两个单词相等的最小删除步数。

      相当于从dp数组定义上删除了i - 1这个字符。

    3. 初始化:dp[i][0]:word2为空字符串,以i-1为结尾的字符串word1要删除多少个元素,才能和word2相同呢,很明显dp[i][0] = idp[0][j]的话同理。

    4. 遍历顺序从前往后,从上往下遍历。

    5. 举例推导dp

      class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int [] [] dp = new int [m + 1][n + 1];for(int i = 0 ; i <= m ; i ++){dp[i][0] = i;}for(int j = 0 ; j <= n ; j ++){dp[0][j] = j;}for(int i = 1 ; i <= m ; i ++){char w1 = word1.charAt(i - 1);for(int j = 1 ; j <= n ; j ++){char w2 = word2.charAt(j - 1);if(w1 == w2) dp[i][j] = dp[i - 1][j - 1];else dp[i][j] = Math.min(dp[i - 1][j] + 1 , dp[i][j - 1] + 1);//System.out.println("以word1[" + (i - 1) + "]和word[" + (j - 1) + "]结尾的单词,最少需要" + dp[i][j] + "步删除才能使word1与word2相等");}}return dp[m][n];}
      }
      
  • 72. 编辑距离 - 力扣(LeetCode)

    1. dp[i][j]:以i - 1结尾的word1和以j - 1结尾的word2,转换所需的最小操作数为dp[i][j]

    2. word1[i - 1] == word2[j - 1] :不需要进行操作,dp[i][j] = dp[i - 1][j - 1]

      word1[i - 1] != word2[j - 1]:需要进行操作:

      删除(添加):word2删除一个元素,相当于word1添加一个元素。

      word1删除一个元素:dp[i][j] = dp[i - 1][j] + 1

      word2删除一个元素(word1添加元素):dp[i][j] = dp[i][j - 1] + 1

      替换:可以回顾一下,if (word1[i - 1] == word2[j - 1])的时候我们的操作 是 dp[i][j] = dp[i - 1][j - 1] 对吧。

      那么只需要一次替换的操作,就可以让 word1[i - 1] 和 word2[j - 1] 相同。所以 dp[i][j] = dp[i - 1][j - 1] + 1;

      这里的替换操作不需要考虑具体细节,只需要想,替换操作就是把不同的数替换为相同的数,比相同时的操作要多一步。

    3. dp数组初始化:dp[i][0] :以下标i-1为结尾的字符串word1,和空字符串word2,最近编辑距离为dp[i][0]

      那么dp[i][0]就应该是i,对word1里的元素全部做删除操作,即:dp[i][0] = i;

      同理dp[0][j] = j;

    4. 从上往下,从左往右遍历。

    5. 举例推导dp数组

      class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int [] [] dp = new int [m + 1][n + 1];for(int i = 0 ; i <= m ; i ++){dp[i][0] = i;}for(int j = 0 ; j <= n ; j ++){dp[0][j] = j;}for(int i = 1 ; i <= m ; i ++){char w1 = word1.charAt(i - 1);for(int j = 1 ; j <= n ; j ++){char w2 = word2.charAt(j - 1);if(w1 == w2) dp[i][j] = dp[i - 1][j - 1];else dp[i][j] = Math.min(dp[i - 1][j - 1] + 1 , Math.min(dp[i - 1][j] + 1 , dp[i][j - 1] + 1));//System.out.println("以word1[" + (i - 1) + "]和word2[" + (j - 1) + "]结尾的单词,word1最少需要" + dp[i][j] + "步操作才能使word1与word2相等");}}return dp[m][n];}
      }
      

总结

  • 392. 判断子序列 - 力扣(LeetCode)对比1143T,1143是两个字符串都可以删元素,而本题如果删元素是删除字符串t,因为只有t有多余的字符串。
  • 115. 不同的子序列 - 力扣(LeetCode),与392. 判断子序列 - 力扣(LeetCode)类似,也是删除元素,并且只能删除其中有多余字符的字符串。不同的是,在s[i - 1]与t[i - 1]相等时,也要考虑不使用s[i - 1]的情况。
  • 583. 两个字符串的删除操作 - 力扣(LeetCode)与1143题思路基本一致。1143题的本质也是删除字符串。
  • 72. 编辑距离 - 力扣(LeetCode)比起删除,多了一步替换的操作,根据word1[i - 1] == word2[j - 1]推导而来,很巧妙。

相关文章:

❤️独特的算法❤️:一文解决编辑距离问题

编辑距离问题 题目关键点115. 不同的子序列 - 力扣&#xff08;LeetCode&#xff09;*dp数组定义&#xff0c;情况讨论583. 两个字符串的删除操作 - 力扣&#xff08;LeetCode&#xff09;两个字符串删除&#xff0c;情况讨论多加一种72. 编辑距离 - 力扣&#xff08;LeetCode…...

三次样条样条:Bézier样条和Hermite样条

总结 What is the Difference Between Natural Cubic Spline, Hermite Spline, Bzier Spline and B-spline? 1.多项式拟合中的 Runge Phenomenon 找到一条通过N1个点的多项式曲线 &#xff0c;需要N次曲线。通过两个点的多项式曲线为一次&#xff0c;三个点的多项式曲线为二…...

Redis面试题 (2023最新版)

文章目录一、Redis为什么快&#xff1f;1、纯内存访问2、单线程&#xff0c;避免上下文切换3、渐进式ReHash、缓存时间戳&#xff08;1&#xff09;渐进式ReHash&#xff1a;&#xff08;2&#xff09;缓存时间戳&#xff1a;二、Redis合适的应用场景常用基本数据类型&#xff…...

基于springboot实现家乡特色食品景点推荐系统【源码+论文】分享

基于springboot实现家乡特色推荐系统演示开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&…...

Spring MVC 启动之 HandlerMapping

在上一篇文章中&#xff0c;我们介绍了 Spring MVC 的启动流程&#xff0c;接下来我们将发分多个篇章详细介绍流程中的重点步骤 今天我们从 HandlerMapping 开始分析&#xff0c;HandlerMapping 是框架中的一个非常重要的组件。它的作用是将URL请求映射到合适的处理程序&#x…...

基于YOLOv5的停车位检测系统(清新UI+深度学习+训练数据集)

摘要&#xff1a;基于YOLOv5的停车位检测系统用于露天停车场车位检测&#xff0c;应用深度学习技术检测停车位是否占用&#xff0c;以辅助停车场对车位进行智能化管理。在介绍算法原理的同时&#xff0c;给出Python的实现代码、训练数据集以及PyQt的UI界面。博文提供了完整的Py…...

【Linux系统编程】5.vim基本操作命令

目录 跳转到指定行 命令模式 末行模式 跳转行首 跳转行尾 自动格式化代码 大括号、中括号、小括号对应 光标移至行首 光标移至行尾 删除单个字符 删除一个单词 删除光标至行尾 删除光标至行首 替换单个字符 删除指定区域 删除指定1行 删除指定多行 复制一行 …...

主流机器学习平台调研与对比分析

梗概 本报告主要调研目前主流的机器学习平台&#xff0c;包括但不限于Amazon的Sage maker&#xff0c;Alibaba的PAI&#xff0c;Baidu的PaddlePaddle。对产品的定位、功能、实践、定价四个方面进行详细解析&#xff0c;并通过标杆对比分析提出一套机器学习平台评价体系&#x…...

作业帮基于明道云开展的硬件业务数字化建设

今天由我代表作业帮来介绍公司在低代码平台应用的一些经验和心得。我今天分享的内容包含两部分&#xff0c;一个是作业帮硬件的介绍&#xff0c;另一个是基于明道云的系统能力建设&#xff0c;也是我们自己总结的经验&#xff0c;希望能给大家带来一些启发。 一、关于作业帮 …...

位图及布隆过滤器的模拟实现与面试题

位图 模拟实现 namespace yyq {template<size_t N>class bitset{public:bitset(){_bits.resize(N / 8 1, 0);//_bits.resize((N >> 3) 1, 0);}void set(size_t x)//将某位做标记{size_t i x / 8; //第几个char对象size_t j x % 8; //这个char对象的第几个比特…...

在 Python 中将天数添加到日期

使用 datetime 模块中的 timedelta() 方法将天数添加到日期中&#xff0c;例如 result_1 date_1 timedelta(days3)。 timedelta 方法可以传递天数参数并将指定的天数添加到日期。 from datetime import datetime, date, timedelta# ✅ 将天数添加到日期 my_str 09-24-2023 …...

vue3知识点

一、vue3带来了什么&#xff1f; 1.性能的提升 打包大小减少41% 初次渲染快55%&#xff0c;更新渲染快133% 内存减少54% 2.源码的升级 使用Proxy代替defineProperty实现响应式 重写虚拟DOM的实现和Tree-shaking 3.拥抱TypeScript Vue3可以更好的支持TypeScript 4.新的特性 4.1.…...

一行代码生成Tableau可视化图表

今天给大家介绍一个十分好用的Python模块&#xff0c;用来给数据集做一个初步的探索性数据分析(EDA)&#xff0c;有着类似Tableau的可视化界面&#xff0c;我们通过对于字段的拖拽就可以实现想要的可视化图表&#xff0c;使用起来十分的简单且容易上手&#xff0c;学习成本低&a…...

链表——删除元素或插入元素(头插法及尾插法)

目录 链表的结点由一个结构体构成 判断链表是否为空 键盘输入链表中的数据 输出链表中的数据 返回链表的元素个数 清空链表 返回指定位置的元素值 查找数据所在位置 删除链表的元素 插入元素 建立无头结点的单链表 建立有头结点的单链表&#xff08;头插法&#xff…...

oracle容器的使用

oracle容器的使用 1.下载oracle容器 1.1拉取容器 docker pull registry.cn-hangzhou.aliyuncs.com/helowin/oracle_11g拉取国内镜像&#xff0c;该镜像大小为2.99G&#xff0c;已经集成了oracle环境&#xff0c;拉取完可以直接用&#xff0c;推荐使用这款oracle镜像 1.2查看…...

基于springboot会员制医疗预约服务管理信息系统演示【附项目源码】

基于springboot会员制医疗预约服务管理信息系统演示开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea M…...

GoogleAdsense国内加载慢怎么解决?

一淘模板 56admin.com 发现GoogleAdsense&#xff08;谷歌广告联盟&#xff09;国内加载慢拖网站速度怎么解决&#xff1f;GoogleAdsense是谷歌旗下的站长广告联盟系统&#xff0c;如果站长没有好的变现渠道&#xff0c;挂谷歌联盟是最好的选择&#xff08;日积月累&#xff09…...

【MySQL专题】03、性能优化之读写分离(MaxScale)

在我们了解了MySQL的主从复制的性能优化之后&#xff0c;紧接着《【MySQL专题】02、性能优化之主从复制》中&#xff0c;我们提及的读写分离&#xff0c;来进行读操作和写操作分散到不同的服务器结构中&#xff0c;同时希望对多个从服务器能提供负载均衡&#xff0c;读写分离和…...

Redis7高级之BigKey(二)

1.MoreKey案例 往redis里面插入大量测试数据key 生成100W条redis批量设置kv的语句保存在redisTest.txt for((i1;i<100*10000;i)); do echo "set k$i v$i" >> /tmp/redisTest.txt ;done; # 生成100W条redis批量设置kv的语句(keykn,valuevn)写入到/tmp目录下的…...

flex弹性盒子

概念 弹性盒子是一种用于按行或者按列布局的一维布局方法&#xff0c;元素可以膨胀以填充额外的空间&#xff0c;缩小以适应更小的空间 以下属性是给父元素添加的 1.flex-direction --改变轴的方向 row 默认值 默认沿着x轴排版(横向从左到右排列&#xff08;左对齐&#xff…...

AWorksLP嵌入式平台FatFs文件系统与SD卡驱动移植实战指南

1. 项目概述&#xff1a;为什么要在AWorksLP上折腾FatFs和SD卡&#xff1f;在嵌入式开发里&#xff0c;存储扩展是个绕不开的话题。尤其是当你手头的MCU片上Flash只有几百KB&#xff0c;却要存点日志、配置文件&#xff0c;甚至是一些小体积的音频、图片资源时&#xff0c;外挂…...

Grid++Report设计器避坑指南:搞不定自动换行和字体缩小?看这篇就够了

GridReport设计器避坑指南&#xff1a;搞不定自动换行和字体缩小&#xff1f;看这篇就够了 当你面对一份需要展示长商品描述、多行地址或其他复杂文本的报表时&#xff0c;是否曾被GridReport的自动换行和字体缩小功能折磨得焦头烂额&#xff1f;作为一款功能强大的报表设计工具…...

Excel公式生成黑科技落地实录(ChatGPT+Power Query+LAMBDA三引擎联动)

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;Excel公式生成黑科技落地实录&#xff08;ChatGPTPower QueryLAMBDA三引擎联动&#xff09; 场景驱动的智能公式生成闭环 当财务团队需在5分钟内为127张销售报表动态生成「跨表多条件加权滚动同比」公…...

技术人的“薪资锚点”策略:第一个报价为什么至关重要?

被低估的“第一印象”在软件测试领域&#xff0c;技术人习惯于与代码、逻辑和数据打交道&#xff0c;往往将薪资谈判视为一种非理性的“讨价还价”。然而&#xff0c;从行为经济学的视角审视&#xff0c;谈判的开局瞬间&#xff0c;其实已经为最终结果划定了无形的边界。那个最…...

当开源代码也成了「敏感物项」

前两天看到一条新闻&#xff1a;英国国民健康服务体系&#xff08;NHS&#xff09;下令关闭数百个 GitHub 仓库&#xff0c;全部设为私有&#xff0c;原因是安全担忧。 不是某个军用级的加密库&#xff0c;不是核设施控制系统的代码——只是一些普通的医疗数据处理工具。但因为…...

Windows内核级硬件指纹伪装终极指南:EASY-HWID-SPOOFER深度解析

Windows内核级硬件指纹伪装终极指南&#xff1a;EASY-HWID-SPOOFER深度解析 【免费下载链接】EASY-HWID-SPOOFER 基于内核模式的硬件信息欺骗工具 项目地址: https://gitcode.com/gh_mirrors/ea/EASY-HWID-SPOOFER 在数字隐私日益重要的今天&#xff0c;硬件指纹识别技术…...

利用Taotoken多模型聚合能力为你的智能客服系统注入活力

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 利用Taotoken多模型聚合能力为你的智能客服系统注入活力 构建一个响应迅速、理解准确且成本可控的智能客服系统&#xff0c;是许多…...

Zynq MPSoC实战:从官方Base TRD里,只抠出HDMI输入+DP显示这一个功能(Vivado 2020.1 + Petalinux)

Zynq MPSoC实战&#xff1a;精准剥离HDMI输入与DP显示功能的工程精简指南 面对Xilinx官方提供的Base TRD参考设计&#xff0c;许多开发者都会被其庞大的规模所震撼——12000行代码、数十个功能模块交织在一起&#xff0c;就像一个功能齐全但臃肿不堪的"瑞士军刀"。本…...

3步完成NCM转MP3:网易云音乐格式转换终极指南

3步完成NCM转MP3&#xff1a;网易云音乐格式转换终极指南 【免费下载链接】ncmdump 项目地址: https://gitcode.com/gh_mirrors/ncmd/ncmdump 你是否曾为网易云音乐下载的NCM格式文件无法在其他设备播放而烦恼&#xff1f;这款开源NCMDump工具为你提供完美的解决方案&a…...

ROS小车转弯卡顿?手把手教你用Python搞定cmd_vel到阿克曼模型的平滑转换

ROS小车转弯卡顿&#xff1f;Python实现cmd_vel到阿克曼模型的平滑转换实战 当你在Gazebo仿真或实际运行ROS控制的阿克曼转向小车时&#xff0c;是否遇到过车体转弯时"一耸一耸"、运动不连贯的尴尬情况&#xff1f;这种卡顿现象往往源于cmd_vel指令到阿克曼运动模型转…...