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

代码随想录算法训练营第五十六天 | 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] + 1
  • dp[i][j] = dp[i][j - 1] + 1
  • dp[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数组&#xff08;dp table&#xff09;以及下标的含义 dp[i][j]&#xff1a;以i-1为结尾的字符串word1&#xff0c;和以j-1位结尾的字符串word2&#xff0c;想要达到相等&#xff0c;所需要删除元素的最少次数。 2、确定递推…...

Sip协议

简介 SIP&#xff08;Session Initiation Protocol&#xff0c;会话初始协议&#xff09;是一个用于建立、更改和终止多媒体会话的应用 层控制协议&#xff0c;其中的会话可以是 IP 电话、多媒体会话或多媒体会议。SIP 是 IETF 多媒体数据和控 制体系结构的核心协议&#xff0…...

RandomAccessFile类 断点续传

文章目录学习链接RandomAccessFile构造方法实现的接口DataOutputDataInputAutoCloseable重要的方法多线程读写同一个文件&#xff08;多线程复制文件&#xff09;代码1代码2断点续传FileUtils学习链接 RandomAccessFile详解 Java IO——RandomAccessFile类详解 java多线程-断点…...

SpringCloud微服务技术栈的注册中心Eureka

文章目录SpringCloud微服务技术栈的注册中心Eureka简介Eureka特点操作步骤环境准备创建Eureka Server注册服务提供方调用服务消费方总结SpringCloud微服务技术栈的注册中心Eureka 简介 在微服务架构中&#xff0c;服务的数量庞大&#xff0c;而且每个服务可能会有多个实例。此…...

Unity最新热更新框架 hybridclr_addressable

GitHub:YMoonRiver/hybridclr_addressable: 开箱即用的商业游戏框架&#xff0c;集成了主流的开发工具。将主流的GameFramework修改&#xff0c;支持Addressable和AssetBundle&#xff0c;已完善打包工具和流程。 (github.com) # 新增GameFramework Addressables 开箱即用 # 新…...

【c语言】一维数组***特性、存储原理

创作不易&#xff0c;本篇文章如果帮助到了你&#xff0c;还请点赞支持一下♡>&#x16966;<)!! 主页专栏有更多知识&#xff0c;如有疑问欢迎大家指正讨论&#xff0c;共同进步&#xff01; 给大家跳段街舞感谢支持&#xff01;ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ…...

[oeasy]python0133_[趣味拓展]好玩的unicode字符_另类字符_上下颠倒英文字符

另类字符 回忆上次内容 上次再次输出了大红心♥ 找到了红心对应的编码黑红梅方都对应有编码 原来的编码叫做 ascii️ \u这种新的编码方式叫unicode包括了 中日韩字符集等 各书写系统的字符集 除了这些常规字符之外 还有什么好玩的东西呢&#xff1f; 颠倒字符 这个网站可以…...

找凶手,定名次,字符串旋转,杨氏矩阵

1.找凶手问题&#xff1a; //题目名称&#xff1a; //猜凶手 //题目内容&#xff1a; //日本某地发生了一件谋杀案&#xff0c;警察通过排查确定凶手必为4个嫌疑犯的一个。 //以下为4个嫌疑犯的供词&#xff1a; //A说&#xff1a;不是我 //B说&#xff1a;是C //C说&#xff…...

Python 进阶指南(编程轻松进阶):十四、实践项目

原文&#xff1a;http://inventwithpython.com/beyond/chapter14.html 到目前为止&#xff0c;这本书已经教会了你编写可读的 Python 风格代码的技巧。让我们通过查看两个命令行游戏的源代码来实践这些技术&#xff1a;汉诺塔和四人一排。 这些项目很短&#xff0c;并且基于文…...

Redis的五种数据类型及应用场景

Redis是一个开源的key-value数据库。 五种数据类型 String&#xff0c;List&#xff0c; Set&#xff0c;SortedSet&#xff0c;Hash List类型可以存储多个String。 Set类型可以存储不同的String。 SortedSet可以存储String的排序。 Hash可以存储多个key-value对。 String …...

c++List的详细介绍

cList详细使用 write in front 作者&#xff1a; 不进大厂不改名 专栏&#xff1a; c 作者简介&#xff1a;大一学生 希望能向其他大佬和同学学习&#xff01; 本篇博客简介&#xff1a;本文主要讲述了一种新容器list的使用方法&#xff0c;相信你在学了后&#xff0c;能够加深…...

Heap堆的升序排序

在heap堆中&#xff0c;大根堆是一种特殊的堆&#xff0c;它满足下列性质&#xff1a;对于任意一个非叶子节点i&#xff0c;其左右子节点的值均小于等于它本身的值。 在大根堆中&#xff0c;堆顶元素永远是值最大的元素&#xff0c;所以将堆顶元素不断取出来&#xff0c;就相当…...

小程序开发收费价目表

小程序作为一种新兴应用形式&#xff0c;正在逐渐成为企业和个人推广、运营的重要手段。然而&#xff0c;小程序开发的价格因项目规模和复杂程度差异较大&#xff0c;令不少人望而却步。本文将从小程序开发的相关因素入手&#xff0c;探讨小程序开发的价格范围和算法。 一、小…...

Dubbo服务暴露步骤详解

文章目录Dubbo服务暴露步骤详解背景介绍理论知识讲解什么是服务暴露&#xff1f;Dubbo 服务暴露的基本原理操作步骤具体实现环境准备实现服务接口实现服务提供者配置 Dubbo 服务提供者启动服务提供者实现服务消费者配置 Dubbo 服务消费者测试总结Dubbo服务暴露步骤详解 背景介…...

第十四届蓝桥杯编程题部分代码题解

C. 冶炼金属 最大值就是取 a/ba / ba/b 的最小值&#xff0c;最小值就是二分找到满足 mid∗(bi1)≥aimid * (b_i 1) ≥ a_imid∗(bi​1)≥ai​ 的最小值 #include<bits/stdc.h> #define int long long #define x first #define y second using namespace std;void sol…...

统一结果封装异常处理

统一结果封装&异常处理2&#xff0c;统一结果封装2.1 表现层与前端数据传输协议定义2.2 表现层与前端数据传输协议实现2.2.1 环境准备2.2.2 结果封装步骤1:创建Result类步骤2:定义返回码Code类步骤3:修改Controller类的返回值步骤4:启动服务测试3&#xff0c;统一异常处理3…...

数字藏品平台的发展趋势是什么?

1、数字藏品平台具体内容生产模式将在PGC&#xff08;专业生产制造具体内容&#xff09;方式向PUGC&#xff08;技术专业用户生产内容&#xff09;方式变化。 目前&#xff0c;中国热门的数字藏品平台都在PGC模式中持续发展的&#xff0c;而国外流行NFT平台则比较多选用UGC&am…...

Vue3对话框(Dialog)

Vue2对话框&#xff08;Dialog&#xff09; 可自定义设置以下属性&#xff1a; 标题&#xff08;title&#xff09;&#xff0c;类型&#xff1a;string | slot&#xff0c;默认 提示 内容&#xff08;content&#xff09;&#xff0c;类型&#xff1a;string | slot&#xf…...

【深度强化学习】(5) DDPG 模型解析,附Pytorch完整代码

大家好&#xff0c;今天和各位分享一下深度确定性策略梯度算法 (Deterministic Policy Gradient&#xff0c;DDPG)。并基于 OpenAI 的 gym 环境完成一个小游戏。完整代码在我的 GitHub 中获得&#xff1a; https://github.com/LiSir-HIT/Reinforcement-Learning/tree/main/Mod…...

unity,Color.Lerp函数

介绍 Color.Lerp函数是Unity引擎中的一个静态函数&#xff0c;用于在两个颜色值之间进行线性插值&#xff0c;从而实现颜色渐变效果 方法 Color.Lerp函数是Unity引擎中的一个静态函数&#xff0c;用于在两个颜色值之间进行线性插值&#xff0c;从而实现颜色渐变效果。该函数的…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...