代码随想录算法训练营第五十六天 | 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结
583. 两个字符串的删除操作
动规五部曲
1、确定dp数组(dp table)以及下标的含义
dp[i][j]:以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等,所需要删除元素的最少次数。
2、确定递推公式
当word1[i - 1] 与 word2[j - 1]相同的时候,dp[i][j] = dp[i - 1][j - 1];
当word1[i - 1] 与 word2[j - 1]不相同的时候,有三种情况:
情况一:删word1[i - 1],最少操作次数为dp[i - 1][j] + 1
情况二:删word2[j - 1],最少操作次数为dp[i][j - 1] + 1
情况三:同时删word1[i - 1]和word2[j - 1],操作的最少次数为dp[i - 1][j - 1] + 2
当word1[i - 1] 与 word2[j - 1]不相同的时候,递推公式:dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2,所以递推公式可简化为:dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
当 同时删word1[i - 1]和word2[j - 1],dp[i][j-1] 本来就不考虑 word2[j - 1]了,那么在删 word1[i - 1],就达到了两个元素都删除的效果,即 dp[i][j-1] + 1
3、dp数组如何初始化
从递推公式中,可以看出来,dp[i][0] 和 dp[0][j]是一定要初始化的。
dp[i][0]:word2为空字符串,以i-1为结尾的字符串word1要删除多少个元素,才能和word2相同呢,很明显dp[i][0] = i。
4、确定遍历顺序
从递推公式 dp[i][j] = min(dp[i - 1][j - 1] + 2, min(dp[i - 1][j], dp[i][j - 1]) + 1); 和dp[i][j] = dp[i - 1][j - 1]可以看出dp[i][j]都是根据左上方、正上方、正左方推出来的。
5、举例推导dp数组
以word1:"sea",word2:"eat"为例,推导dp数组状态图如下:

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;for (int i = 1; i <= word1.size(); i++) {for (int j = 1; j <= word2.size(); 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, dp[i][j - 1] + 1);}}}return dp[word1.size()][word2.size()];}
};
思路二
只要求出两个字符串的最长公共子序列长度即可,那么除了最长公共子序列之外的字符都是必须删除的,最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));for (int i = 1; i <= word1.size(); i++) {for (int j = 1; j <= word2.size(); j++) {if (word1[i - 1] == word2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return word1.size() + word2.size() - dp[word1.size()][word2.size()] * 2;}
};
72. 编辑距离
动规五部曲
1、确定dp数组(dp table)以及下标的含义
dp[i][j] 表示以下标i-1为结尾的字符串word1,和以下标j-1为结尾的字符串word2,最近编辑距离为dp[i][j]。
2、确定递推公式
在确定递推公式的时候,首先要考虑清楚编辑的几种操作,整理如下:
if (word1[i - 1] == word2[j - 1])不操作
if (word1[i - 1] != word2[j - 1])增删换
if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑,dp[i][j] 就应该是 dp[i - 1][j - 1],即dp[i][j] = dp[i - 1][j - 1];
if (word1[i - 1] != word2[j - 1])
- 操作一:word1删除一个元素,那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] = dp[i - 1][j] + 1;
- 操作二:word2删除一个元素,那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] = dp[i][j - 1] + 1;
word2添加一个元素,相当于word1删除一个元素,例如 word1 = "ad" ,word2 = "a",word1删除元素'd' 和 word2添加一个元素'd',变成word1="a", word2="ad"
操作三:替换元素,word1替换word1[i - 1],使其与word2[j - 1]相同,此时不用增删加元素。
当 if (word1[i - 1] != word2[j - 1]) 时取最小的,即:dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][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、确定遍历顺序
从如下四个递推公式:
dp[i][j] = dp[i - 1][j - 1]dp[i][j] = dp[i - 1][j - 1] + 1dp[i][j] = dp[i][j - 1] + 1dp[i][j] = dp[i - 1][j] + 1
可以看出dp[i][j]是依赖左方,上方和左上方元素的,如图:

所以在dp矩阵中一定是从左到右从上到下去遍历。
5、举例推导dp数组
以示例1为例,输入:word1 = "horse", word2 = "ros"为例,dp矩阵状态图如下:

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;for (int i = 1; i <= word1.size(); i++) {for (int j = 1; j <= word2.size(); 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], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;}}}return dp[word1.size()][word2.size()];}
};
编辑距离总结
编辑距离从判断子序列->判断子序列 ->不同的子序列 ->两个字符串的删除操作->编辑距离
以上四个题都是从最初子序列开始,在原本一个子序列的基础上,变成了二维,通过观察每次解题代码可以发现,其实各题在解题思路上都几乎类似,难点在于递推公式的推导与初始化,递推公式的推导要在理解各题要求的同时,思考该如何得出当前状态,时刻谨记dp数组的定义有利于递推公式推导
相关文章:
代码随想录算法训练营第五十六天 | 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结
583. 两个字符串的删除操作 动规五部曲 1、确定dp数组(dp table)以及下标的含义 dp[i][j]:以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等,所需要删除元素的最少次数。 2、确定递推…...
Sip协议
简介 SIP(Session Initiation Protocol,会话初始协议)是一个用于建立、更改和终止多媒体会话的应用 层控制协议,其中的会话可以是 IP 电话、多媒体会话或多媒体会议。SIP 是 IETF 多媒体数据和控 制体系结构的核心协议࿰…...
RandomAccessFile类 断点续传
文章目录学习链接RandomAccessFile构造方法实现的接口DataOutputDataInputAutoCloseable重要的方法多线程读写同一个文件(多线程复制文件)代码1代码2断点续传FileUtils学习链接 RandomAccessFile详解 Java IO——RandomAccessFile类详解 java多线程-断点…...
SpringCloud微服务技术栈的注册中心Eureka
文章目录SpringCloud微服务技术栈的注册中心Eureka简介Eureka特点操作步骤环境准备创建Eureka Server注册服务提供方调用服务消费方总结SpringCloud微服务技术栈的注册中心Eureka 简介 在微服务架构中,服务的数量庞大,而且每个服务可能会有多个实例。此…...
Unity最新热更新框架 hybridclr_addressable
GitHub:YMoonRiver/hybridclr_addressable: 开箱即用的商业游戏框架,集成了主流的开发工具。将主流的GameFramework修改,支持Addressable和AssetBundle,已完善打包工具和流程。 (github.com) # 新增GameFramework Addressables 开箱即用 # 新…...
【c语言】一维数组***特性、存储原理
创作不易,本篇文章如果帮助到了你,还请点赞支持一下♡>𖥦<)!! 主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步! 给大家跳段街舞感谢支持!ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ…...
[oeasy]python0133_[趣味拓展]好玩的unicode字符_另类字符_上下颠倒英文字符
另类字符 回忆上次内容 上次再次输出了大红心♥ 找到了红心对应的编码黑红梅方都对应有编码 原来的编码叫做 ascii️ \u这种新的编码方式叫unicode包括了 中日韩字符集等 各书写系统的字符集 除了这些常规字符之外 还有什么好玩的东西呢? 颠倒字符 这个网站可以…...
找凶手,定名次,字符串旋转,杨氏矩阵
1.找凶手问题: //题目名称: //猜凶手 //题目内容: //日本某地发生了一件谋杀案,警察通过排查确定凶手必为4个嫌疑犯的一个。 //以下为4个嫌疑犯的供词: //A说:不是我 //B说:是C //C说ÿ…...
Python 进阶指南(编程轻松进阶):十四、实践项目
原文:http://inventwithpython.com/beyond/chapter14.html 到目前为止,这本书已经教会了你编写可读的 Python 风格代码的技巧。让我们通过查看两个命令行游戏的源代码来实践这些技术:汉诺塔和四人一排。 这些项目很短,并且基于文…...
Redis的五种数据类型及应用场景
Redis是一个开源的key-value数据库。 五种数据类型 String,List, Set,SortedSet,Hash List类型可以存储多个String。 Set类型可以存储不同的String。 SortedSet可以存储String的排序。 Hash可以存储多个key-value对。 String …...
c++List的详细介绍
cList详细使用 write in front 作者: 不进大厂不改名 专栏: c 作者简介:大一学生 希望能向其他大佬和同学学习! 本篇博客简介:本文主要讲述了一种新容器list的使用方法,相信你在学了后,能够加深…...
Heap堆的升序排序
在heap堆中,大根堆是一种特殊的堆,它满足下列性质:对于任意一个非叶子节点i,其左右子节点的值均小于等于它本身的值。 在大根堆中,堆顶元素永远是值最大的元素,所以将堆顶元素不断取出来,就相当…...
小程序开发收费价目表
小程序作为一种新兴应用形式,正在逐渐成为企业和个人推广、运营的重要手段。然而,小程序开发的价格因项目规模和复杂程度差异较大,令不少人望而却步。本文将从小程序开发的相关因素入手,探讨小程序开发的价格范围和算法。 一、小…...
Dubbo服务暴露步骤详解
文章目录Dubbo服务暴露步骤详解背景介绍理论知识讲解什么是服务暴露?Dubbo 服务暴露的基本原理操作步骤具体实现环境准备实现服务接口实现服务提供者配置 Dubbo 服务提供者启动服务提供者实现服务消费者配置 Dubbo 服务消费者测试总结Dubbo服务暴露步骤详解 背景介…...
第十四届蓝桥杯编程题部分代码题解
C. 冶炼金属 最大值就是取 a/ba / ba/b 的最小值,最小值就是二分找到满足 mid∗(bi1)≥aimid * (b_i 1) ≥ a_imid∗(bi1)≥ai 的最小值 #include<bits/stdc.h> #define int long long #define x first #define y second using namespace std;void sol…...
统一结果封装异常处理
统一结果封装&异常处理2,统一结果封装2.1 表现层与前端数据传输协议定义2.2 表现层与前端数据传输协议实现2.2.1 环境准备2.2.2 结果封装步骤1:创建Result类步骤2:定义返回码Code类步骤3:修改Controller类的返回值步骤4:启动服务测试3,统一异常处理3…...
数字藏品平台的发展趋势是什么?
1、数字藏品平台具体内容生产模式将在PGC(专业生产制造具体内容)方式向PUGC(技术专业用户生产内容)方式变化。 目前,中国热门的数字藏品平台都在PGC模式中持续发展的,而国外流行NFT平台则比较多选用UGC&am…...
Vue3对话框(Dialog)
Vue2对话框(Dialog) 可自定义设置以下属性: 标题(title),类型:string | slot,默认 提示 内容(content),类型:string | slot…...
【深度强化学习】(5) DDPG 模型解析,附Pytorch完整代码
大家好,今天和各位分享一下深度确定性策略梯度算法 (Deterministic Policy Gradient,DDPG)。并基于 OpenAI 的 gym 环境完成一个小游戏。完整代码在我的 GitHub 中获得: https://github.com/LiSir-HIT/Reinforcement-Learning/tree/main/Mod…...
unity,Color.Lerp函数
介绍 Color.Lerp函数是Unity引擎中的一个静态函数,用于在两个颜色值之间进行线性插值,从而实现颜色渐变效果 方法 Color.Lerp函数是Unity引擎中的一个静态函数,用于在两个颜色值之间进行线性插值,从而实现颜色渐变效果。该函数的…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...
Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...
【堆垛策略】设计方法
堆垛策略的设计是积木堆叠系统的核心,直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法,涵盖基础规则、优化算法和容错机制: 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则: 大尺寸/重量积木在下…...
倒装芯片凸点成型工艺
UBM(Under Bump Metallization)与Bump(焊球)形成工艺流程。我们可以将整张流程图分为三大阶段来理解: 🔧 一、UBM(Under Bump Metallization)工艺流程(黄色区域ÿ…...
Linux操作系统共享Windows操作系统的文件
目录 一、共享文件 二、挂载 一、共享文件 点击虚拟机选项-设置 点击选项,设置文件夹共享为总是启用,点击添加,可添加需要共享的文件夹 查询是否共享成功 ls /mnt/hgfs 如果显示Download(这是我共享的文件夹)&…...
