第五十五天| 583. 两个字符串的删除操作、72. 编辑距离

news/2024/5/30 1:39:39/文章来源:https://blog.csdn.net/Adore_master/article/details/136720006

Leetcode 583. 两个字符串的删除操作

题目链接:583 两个字符串的删除操作

题干:给定两个单词 word1 和 word2 ,返回使得 word1 和  word2 相同所需的最小步数

每步 可以删除任意一个字符串中的一个字符。

思考:动态规划。本题中的步数可以看作删除字母,使得两单词最终处理为相同字母组。

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

dp[i][j]:使得 以i - 1结尾的单词word1和以j - 1结尾的单词word2 相同所需的最小步数。

  • 确定递推公式

从dp[i][j]的定义可以看出,字母比较就两种情况

  • 当word1[i - 1] 与 word2[j - 1]相同的时候
  • 当word1[i - 1] 与 word2[j - 1]不相同的时候

当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);

  • dp数组如何初始化

从递推公式中,可以看出来,dp[i][0] 和 dp[0][j]是一定要初始化的。

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

  • 确定遍历顺序

从递推公式 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1; 和dp[i][j] = dp[i - 1][j - 1]可以看出dp[i][j]都是根据左上方、正上方、正左方推出来的。

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

  • 举例推导dp数组

举例:word1:"sea",word2:"eat",推导dp数组状态图如下:

代码:

class Solution {
public:int minDistance(string word1, string word2) {//dp[i][j]:使得 以i - 1结尾的单词word1和以j - 1结尾的单词word2 相同所需的最小步数 vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));for (int i = 1; i <= word1.size(); i++)     //单词word2为空的情况dp[i][0] = i;for (int j = 1; j <= word2.size(); j++)     //单词word1为空的情况dp[0][j] = j;for (int i = 1; i <= word1.size(); i++) {           //遍历单词word1for(int j = 1; j <= word2.size(); j++) {        //遍历单词word2if (word1[i - 1] == word2[j - 1])dp[i][j] = dp[i - 1][j - 1];        //字母相同则无需无需删除字母elsedp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 1;     //字母不相同则选一单词删除字母,取最小值}}return dp[word1.size()][word2.size()];}
};

思考:动态规划。本题也可以从求公共子序列入手,要删除的元素个数(即步数)为两单词长度减去两倍公共子序列长度。具体如何求公共子序列:1143 最长公共子序列

代码: 

class Solution {
public:int minDistance(string word1, string word2) {//dp[i][j]:单词word1的处理区间[0, i - 1]与单词word2的处理区间[0, j - 1]中,存在的最长公共子序列的长度vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));     for (int i = 1; i <= word1.size(); i++) {           //遍历单词word1for (int j = 1; j <= word2.size(); j++) {       //遍历单词word2if (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() - 2 * dp[word1.size()][word2.size()];        //两单词去除最长公共子序列}
};

Leetcode 72. 编辑距离

题目链接:72 编辑距离

题干:给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数  。你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

思考:动态规划。本题要先想清楚:真正要求的是将word1和word2变成相同单词的操作次数。

题干中删除word1字母的操作 可以等价为 插入word2字母的操作;插入word1字母的操作 可以等价为 删除word2字母的操作。下面就直接考虑删除操作不考虑插入操作。

因此本题与上题的区别在 确定递推公式中:

当word1[i - 1] 与 word2[j - 1]不相同的时候,有不同的三种操作:

情况一:删word1[i - 1],最少操作次数为dp[i - 1][j] + 1

情况二:删word2[j - 1](同向word1中插入),最少操作次数为dp[i][j - 1] + 1

情况三:替换word1[i - 1],最少的操作次数为dp[i - 1][j - 1] + 1

当然要取最小值,所以当word1[i - 1] 与 word2[j - 1]不相同的时候,递推公式:dp[i][j] = min({dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

代码:

class Solution {
public:int minDistance(string word1, string word2) {//dp[i][j]:对以i- 1结尾的单词word1和以j - 1结尾的单词word2操作,让处理后两单词相同的最少操作次数vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));for (int i = 0; i <= word1.size(); i++)     //单词word2为空的情况dp[i][0] = i;for (int j = 1; j <= word2.size(); j++)     //单词word1为空的情况dp[0][j] = j;for (int i = 1; i <= word1.size(); i++) {           //遍历单词word1for (int j = 1; j <= word2.size(); j++) {       //遍历单词word2if (word1[i - 1] == word2[j - 1])//当前两字母相同则不用处理dp[i][j] = dp[i - 1][j - 1];    else//当前两字母不同则考虑替换word1的字母,删除word1的字母以及删除word2的字母dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j -1])) + 1;}}return dp[word1.size()][word2.size()];}
};

自我总结:

        理解公共子序列问题的关键在于删除操作,两字符串的操作含义同dp数组的含义变化而变化。动态规划是在每次操作中考虑每种情况,统一处理。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1007178.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

WebPack自动吐出脚本

window.c c; window.res ""; window.flag false;c function (r) {if (flag) {window.res window.res "${r.toString()}" ":" (e[r] "") ",";}return window.c(r); }代码改进了一下&#xff0c;可以过滤掉重复的方…

【Java并发知识总结 | 第二篇】乐观锁和悲观锁详讲

文章目录 2.乐观锁和悲观锁详讲2.1悲观锁2.2乐观锁2.3如何实现乐观锁2.3.1版本号机制2.3.2CAS算法2.3.3CAS底层 2.4乐观锁存在的问题2.4.1ABA问题&#xff08;1&#xff09;问题描述&#xff08;2&#xff09;解决 2.4.2循环时间长、开销大2.4.3只能保证一个共享变量的原子操作…

Remove Prefix

题目链接&#xff1a;Problem - B - Codeforces 解题思路&#xff1a; 从最后开始遍历&#xff0c;用map记录每个数出现的次数&#xff0c;再定义一个num记录遍历的次数&#xff0c;要是没超过1&#xff0c;次数加一&#xff0c;超过就结束循环&#xff0c;输出数组长度减去nu…

新 树莓派4B 温湿度监测 基于debian12的树莓派OS

前言 本文旨在完成通过外接温湿度传感器至树莓派使得树莓派不断记录并存储温湿度数据 这个领域有很多文章&#xff0c;但是部分文章已经缺乏了时效性&#xff0c;在最新系统不适用&#xff0c;本文目前适用 硬件 硬件连接 温湿度传感器常选用DHT11和DHT22&#xff0c;淘宝…

maven打包把所有依赖的jar copy到一个文件夹

在maven项目中&#xff0c;是使用依赖坐标来引入jar包&#xff0c;在引入jar包的时候&#xff0c;maven也会默默的帮助我们导入这个jar包所依赖的jar包。 但是当我们打包项目使用jar包运行的时候&#xff0c;往往会出现缺少jar的情况&#xff1a; 如果我们一个一个添加缺少的…

基于单片机的恒压供水控制器设计

摘 要 随着我国现代化的进程不断加快&#xff0c;城市居民生活水平不断提高&#xff0c;随之而来的是房屋的翻新和重建&#xff0c;但建筑层数的不断增高&#xff0c;使得供水所需压力不断提高&#xff0c;若建筑设计时对压力判断不足&#xff0c;会导致供水时无法供应到高楼层…

Retrofit

1.导入依赖 //Retrofit 核心库implementation("com.squareup.retrofit2:retrofit:2.9.0")//响应数据自动序列化//JSONimplementation("com.squareup.retrofit2:converter-gson:2.9.0")//String类型implementation("com.squareup.retrofit2:converter…

技术派整合MyBatis-Plus

Mybatis-Plus大家都熟悉了吧&#xff1f;是一个Mybatis的增强&#xff0c;提供了一些额外功能&#xff0c;比如条件构造器、分页插件、代码生成器等以便我们更专注于业务&#xff0c;而不是SQL语句的编写 官方教程&#xff1a;简介 | MyBatis-Plus 整合MyBatis-Plus 非常简单…

ThreadLocal基本原理

ThreadLocal基本原理 一、定义 ThreadLocal是java中所提供的线程本地存储机制&#xff0c;可以利用改机制将数据缓存在线程内部&#xff0c;该线程可以在任意时刻、任意方法中获取数据 二、底层原理 ThreadLocal底层是通过ThreadLocalMap来实现的&#xff0c;每个Thread对象中…

【数据结构与算法】:插入排序与希尔排序

&#x1f525;个人主页&#xff1a; Quitecoder &#x1f525;专栏: 数据结构与算法 欢迎大家来到初阶数据结构的最后一小节&#xff1a;排序 目录 1.排序的基本概念与分类1.1什么是排序的稳定性&#xff1f;1.2内排序与外排序内排序外排序 2.插入排序2.1实现插入排序2.3稳定性…

【Pytorch】进阶学习:基于矩阵乘法torch.matmul()实现全连接层

【Pytorch】进阶学习&#xff1a;基于矩阵乘法torch.matmul()实现全连接层 &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程&#x1f448…

19、设计模式之中介者模式(Mediator)

一、什么是中介者模式 中介者模式是一种行为型设计模式&#xff0c;它用于减少对象之间互相通信的复杂性。中介者模式通过创建一个中介者对象&#xff0c;将对象之间的通信集中交给该对象来处理&#xff0c;而不是直接相互交流&#xff0c;是符合迪米特原则的典型应用。 迪米特…

物理机win10怎么与虚拟机win10共享文件

打开win10虚拟机点击虚拟机选项安装vmTools 安装完成后系统会重启重启后关机 点击编辑虚拟机设置 选项、共享文件夹、总是启用 接下来点击添加选择你要共享的文件点击确定 打开虚拟机点击此电脑 就会看到共享的文件夹啦

Milvus的相似度指标

官网&#xff1a;https://milvus.io/docs/metric.md版本: v2.3.x 在 Milvus 中&#xff0c;相似度度量用于衡量向量之间的相似度。选择良好的距离度量有助于显着提高分类和聚类性能。下表展示了这些广泛使用的相似性指标如何与各种输入数据形式和 Milvus 索引相匹配。 一、浮…

【C#图解教程】笔记

文章目录 1. C#和.NET框架.NET框架的组成.NET框架的特点CLRCLICLI的重要组成部分各种缩写 2. C#编程概括标识符命名规则&#xff1a; 多重标记和值格式化数字字符串对齐说明符格式字段标准数字格式说明符标准数字格式说明符 表 3. 类型、存储和变量数据成员和函数成员预定义类型…

第二门课:改善深层神经网络<超参数调试、正则化及优化>-深度学习的实用层面

文章目录 1 训练集、验证集以及测试集2 偏差与方差3 机器学习基础4 正则化5 为什么正则化可以减少过拟合&#xff1f;6 Dropout<随机失活>正则化7 理解Dropout8 其他正则化方法9 归一化输入10 梯度消失和梯度爆炸11 神经网络的权重初始化12 梯度的数值逼近13 梯度检验14 …

IDEA自定义Maven仓库

Maven 是一款广泛应用于 Java 开发的工具&#xff0c;其作用类似于一个全自动的 JAR 包管理器&#xff0c;能够方便地导入开发所需的相关 JAR 包。在使用 Maven 进行 Java 程序开发时&#xff0c;开发者能够极大地提高开发效率。以下是关于如何安装 Maven 以及在 IDEA 中配置自…

iOS——【自动引用计数】ARC规则及实现

1.3.3所有权修饰符 所有权修饰符一共有四种&#xff1a; __strong 修饰符__weak 修饰符__undafe_unretained 修饰符__autoreleasing 修饰符 __strong修饰符 _strong修饰符表示对对象的强引用&#xff0c;持有强引用的变量在超出其作用域的时候会被废弃&#xff0c;随着强引…

③【Docker】Docker部署Nginx

个人简介&#xff1a;Java领域新星创作者&#xff1b;阿里云技术博主、星级博主、专家博主&#xff1b;正在Java学习的路上摸爬滚打&#xff0c;记录学习的过程~ 个人主页&#xff1a;.29.的博客 学习社区&#xff1a;进去逛一逛~ ③【Docker】Docker部署Nginx docker拉取nginx…

二、应用层

二、应用层 2.1 应用层协议原理 可能用的应用架构&#xff1a; 1.C/S模式&#xff1a;用户增加&#xff0c;性能断崖式下降 2.P2P体系结构 3.混合体 进程通信&#xff1a; 进程—在主机上运行的应用程序 在同一个主机内&#xff0c;使用进程间通信机制通信&#xff08;操作…