❤️独特的算法❤️:一文解决编辑距离问题
编辑距离问题
题目 | 关键点 |
---|---|
115. 不同的子序列 - 力扣(LeetCode)* | dp数组定义,情况讨论 |
583. 两个字符串的删除操作 - 力扣(LeetCode) | 两个字符串删除,情况讨论多加一种 |
72. 编辑距离 - 力扣(LeetCode) | 删除 == 添加 、替换操作? |
-
115. 不同的子序列 - 力扣(LeetCode)
-
确定dp数组(dp table)以及下标的含义
dp[i][j]
:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
。这样定义,注定s中要删除元素,满足t的条件。比如s:bagg,t:bag,那么就需要s中删除元素满足t的条件。
本题刚开始的dp数组定义就与之前子序列的定义不同,所以分析方法也不同。
-
确定递推公式:这一类问题,基本是要分析两种情况
-
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]来匹配,那么个数不变,还是看上一个序列的个数
-
s[i - 1] 与 t[j - 1] 不相等
dp[i][j]
只有一部分组成,不用s[i - 1]来匹配(就是模拟在s中删除这个元素),即:dp[i - 1][j]
所以递推公式为:
dp[i][j] = dp[i - 1][j];
-
-
-
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。
-
-
遍历的时候一定是从上到下,从左到右,这样保证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)
-
dp定义:
dp[i][j]
:以i - 1结尾的word1和以j - 1结尾的word2,删除字符后使两个单词相等的最小删除步数为dp[i][j]
。 -
dp数组推导:
word1[i - 1] = word2[j - 1]:不需要删除:
dp[i][j] = dp[i - 1][j - 1]
。word1[i - 1] != word2[j - 1]:需要删除:删除word1或删除word2
dp[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这个字符。
-
初始化:
dp[i][0]
:word2为空字符串,以i-1为结尾的字符串word1要删除多少个元素,才能和word2相同呢,很明显dp[i][0] = i
。dp[0][j]
的话同理。 -
遍历顺序从前往后,从上往下遍历。
-
举例推导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)
-
dp[i][j]
:以i - 1结尾的word1和以j - 1结尾的word2,转换所需的最小操作数为dp[i][j]
。 -
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;
这里的替换操作不需要考虑具体细节,只需要想,替换操作就是把不同的数替换为相同的数,比相同时的操作要多一步。
-
dp数组初始化:
dp[i][0]
:以下标i-1为结尾的字符串word1,和空字符串word2,最近编辑距离为dp[i][0]
。那么
dp[i][0]
就应该是i,对word1里的元素全部做删除操作,即:dp[i][0] = i;
同理
dp[0][j] = j;
-
从上往下,从左往右遍历。
-
举例推导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. 不同的子序列 - 力扣(LeetCode)*dp数组定义,情况讨论583. 两个字符串的删除操作 - 力扣(LeetCode)两个字符串删除,情况讨论多加一种72. 编辑距离 - 力扣(LeetCode…...

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

Redis面试题 (2023最新版)
文章目录一、Redis为什么快?1、纯内存访问2、单线程,避免上下文切换3、渐进式ReHash、缓存时间戳(1)渐进式ReHash:(2)缓存时间戳:二、Redis合适的应用场景常用基本数据类型ÿ…...

基于springboot实现家乡特色食品景点推荐系统【源码+论文】分享
基于springboot实现家乡特色推荐系统演示开发语言:Java 框架:springboot JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7 数据库工具:Navicat11 开发软件:eclipse/myeclipse/idea Maven包&…...

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

基于YOLOv5的停车位检测系统(清新UI+深度学习+训练数据集)
摘要:基于YOLOv5的停车位检测系统用于露天停车场车位检测,应用深度学习技术检测停车位是否占用,以辅助停车场对车位进行智能化管理。在介绍算法原理的同时,给出Python的实现代码、训练数据集以及PyQt的UI界面。博文提供了完整的Py…...
【Linux系统编程】5.vim基本操作命令
目录 跳转到指定行 命令模式 末行模式 跳转行首 跳转行尾 自动格式化代码 大括号、中括号、小括号对应 光标移至行首 光标移至行尾 删除单个字符 删除一个单词 删除光标至行尾 删除光标至行首 替换单个字符 删除指定区域 删除指定1行 删除指定多行 复制一行 …...

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

作业帮基于明道云开展的硬件业务数字化建设
今天由我代表作业帮来介绍公司在低代码平台应用的一些经验和心得。我今天分享的内容包含两部分,一个是作业帮硬件的介绍,另一个是基于明道云的系统能力建设,也是我们自己总结的经验,希望能给大家带来一些启发。 一、关于作业帮 …...
位图及布隆过滤器的模拟实现与面试题
位图 模拟实现 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() 方法将天数添加到日期中,例如 result_1 date_1 timedelta(days3)。 timedelta 方法可以传递天数参数并将指定的天数添加到日期。 from datetime import datetime, date, timedelta# ✅ 将天数添加到日期 my_str 09-24-2023 …...

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

一行代码生成Tableau可视化图表
今天给大家介绍一个十分好用的Python模块,用来给数据集做一个初步的探索性数据分析(EDA),有着类似Tableau的可视化界面,我们通过对于字段的拖拽就可以实现想要的可视化图表,使用起来十分的简单且容易上手,学习成本低&a…...
链表——删除元素或插入元素(头插法及尾插法)
目录 链表的结点由一个结构体构成 判断链表是否为空 键盘输入链表中的数据 输出链表中的数据 返回链表的元素个数 清空链表 返回指定位置的元素值 查找数据所在位置 删除链表的元素 插入元素 建立无头结点的单链表 建立有头结点的单链表(头插法ÿ…...

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

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

GoogleAdsense国内加载慢怎么解决?
一淘模板 56admin.com 发现GoogleAdsense(谷歌广告联盟)国内加载慢拖网站速度怎么解决?GoogleAdsense是谷歌旗下的站长广告联盟系统,如果站长没有好的变现渠道,挂谷歌联盟是最好的选择(日积月累)…...
【MySQL专题】03、性能优化之读写分离(MaxScale)
在我们了解了MySQL的主从复制的性能优化之后,紧接着《【MySQL专题】02、性能优化之主从复制》中,我们提及的读写分离,来进行读操作和写操作分散到不同的服务器结构中,同时希望对多个从服务器能提供负载均衡,读写分离和…...

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

接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...

Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...

20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...

免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...