❤️独特的算法❤️:一文解决编辑距离问题
编辑距离问题
题目 | 关键点 |
---|---|
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轴排版(横向从左到右排列(左对齐ÿ…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...