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

代码随想录算法训练营第56天 | ● 583. 两个字符串的删除操作 ● 72. 编辑距离 ● 动态规划之编辑距离总结篇

文章目录

  • 前言
  • 一、583. 两个字符串的删除操作
  • 二、72. 编辑距离
  • 三、动态规划之编辑距离总结篇
  • 总结

前言


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

两种思路:1.直接动态规划,求两个字符串需要删除的最小次数 2.采用子序列的和-最长公共子序列。思路一分析如下:

动规五部曲,分析如下:

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

dp[i][j]:以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等,所需要删除元素的最少次数。

这里dp数组的定义有点点绕,大家要撸清思路。

  1. 确定递推公式
  • 当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);

这里可能不少录友有点迷糊,从字面上理解 就是 当 同时删word1[i - 1]和word2[j - 1],dp[i][j-1] 本来就不考虑 word2[j - 1]了,那么我在删 word1[i - 1],是不是就达到两个元素都删除的效果,即 dp[i][j-1] + 1。

  1. dp数组如何初始化

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

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

  1. 确定遍历顺序

从递推公式 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]都是根据左上方、正上方、正左方推出来的。

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

  1. 举例推导dp数组

代码(思路一):

关键代码:

dp[i][j] = Math.min(dp[i - 1][j - 1] + 2, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));

优化代码:

dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);

class Solution {public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1+1][len2+1];for(int i =1;i<=len1;i++){dp[i][0] = i; }for(int j = 1;j<=len2;j++){dp[0][j] = j;}for(int i = 1;i<=len1;i++){for(int j =1;j<=len2;j++){if(word1.charAt(i-1) == word2.charAt(j-1)){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = Math.min(dp[i][j-1]+1,dp[i-1][j]+1);}}}return dp[len1][len2];}
}

代码(思路二):

class Solution {public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1+1][len2+1];for(int i = 1;i<= len1;i++){for(int j = 1;j<= len2;j++){if(word1.charAt(i-1) == word2.charAt(j-1)){dp[i][j] = dp[i-1][j-1] +1;}else{dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}}return len1 + len2 - 2*dp[len1][len2];}
}

二、72. 编辑距离

因为前面的铺垫,这题显得并不困难,难点在于理解;另外,本题的代码基本复制的上一题的解法一,只更改了了一行代码:

dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));

 因为题解基本一致,这里只提及了最有差异的递推公式的解:

确定递推公式

在确定递推公式的时候,首先要考虑清楚编辑的几种操作,整理如下:

if (word1[i - 1] == word2[j - 1])不操作
if (word1[i - 1] != word2[j - 1])增删换

也就是如上4种情况。

if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑,dp[i][j] 就应该是 dp[i - 1][j - 1],即dp[i][j] = dp[i - 1][j - 1];

此时可能有同学有点不明白,为啥要即dp[i][j] = dp[i - 1][j - 1]呢?

那么就在回顾上面讲过的dp[i][j]的定义,word1[i - 1]word2[j - 1]相等了,那么就不用编辑了,以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp[i - 1][j - 1]就是 dp[i][j]了。

在下面的讲解中,如果哪里看不懂,就回想一下dp[i][j]的定义,就明白了。

在整个动规的过程中,最为关键就是正确理解dp[i][j]的定义!

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", 最终的操作数是一样! dp数组如下图所示意的:

            a                         a     d+-----+-----+             +-----+-----+-----+|  0  |  1  |             |  0  |  1  |  2  |+-----+-----+   ===>      +-----+-----+-----+a |  1  |  0  |           a |  1  |  0  |  1  |+-----+-----+             +-----+-----+-----+d |  2  |  1  |+-----+-----+

操作三:替换元素,word1替换word1[i - 1],使其与word2[j - 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;

综上,当 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;

递归公式代码如下:

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 - 1][j], dp[i][j - 1]}) + 1;
}
class Solution {public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1+1][len2+1];for(int i =1;i<=len1;i++){dp[i][0] = i; }for(int j = 1;j<=len2;j++){dp[0][j] = j;}for(int i = 1;i<=len1;i++){for(int j =1;j<=len2;j++){if(word1.charAt(i-1) == word2.charAt(j-1)){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = Math.min(dp[i-1][j-1]+1,Math.min(dp[i][j-1]+1,dp[i-1][j]+1));}}}return dp[len1][len2];}
}

三、动态规划之编辑距离总结篇

考虑动态规划,首先明确dp数组以及下标的含义(如果是i-1,j-1,考虑一下好处),随后是递推公式,这里需要对两个字符串(因为基本是字符串数组)的前后操作进行思考,接着进行初始化,初始化会因为dp数组的含义不同而不同;其次是根据递推公式确定遍历顺序,因此最后一步打印dp数组也成为检验的重要一步。


总结

动态规划。

相关文章:

代码随想录算法训练营第56天 | ● 583. 两个字符串的删除操作 ● 72. 编辑距离 ● 动态规划之编辑距离总结篇

文章目录 前言一、583. 两个字符串的删除操作二、72. 编辑距离三、动态规划之编辑距离总结篇总结 前言 一、583. 两个字符串的删除操作 两种思路&#xff1a;1.直接动态规划&#xff0c;求两个字符串需要删除的最小次数 2.采用子序列的和-最长公共子序列。思路一分析如下&#…...

矩阵 m * M = c

文章目录 题1题2 题1 (2023江苏领航杯-prng) 题目来源&#xff1a;https://dexterjie.github.io/2023/09/12/%E8%B5%9B%E9%A2%98%E5%A4%8D%E7%8E%B0/2023%E9%A2%86%E8%88%AA%E6%9D%AF/ 题目描述&#xff1a; (没有原数据&#xff0c;自己生成的数据) from Crypto.Util.number…...

Linux——IO

✅<1>主页&#xff1a;&#xff1a;我的代码爱吃辣 &#x1f4c3;<2>知识讲解&#xff1a;Linux——文件系统 ☂️<3>开发环境&#xff1a;Centos7 &#x1f4ac;<4>前言&#xff1a;是不是只有C/C有文件操作呢&#xff1f;python&#xff0c;java&…...

svn(乌龟svn)和SVN-VS2022插件(visualsvn) 下载

下载地址: https://www.visualsvn.com/visualsvn/download/...

开源日报 0824 | 构建UI组件和页面的前端工作坊

Storybook 是一个用于构建 UI 组件和页面的前端工作坊&#xff0c;支持多种主流框架&#xff0c;提供丰富的插件&#xff0c;具有可配置性强和扩展性好的特点。 storybookjs/storybook Stars: 79.9k License: MIT Storybook 是一个用于构建 UI 组件和页面的前端工作坊&#x…...

福建三明大型工程机械3D扫描工程零件三维建模逆向抄数-CASAIM中科广电

高精度3D扫描技术已经在大型工件制造领域发挥着重要作用&#xff0c;可以高精度高效率实现全尺寸三维测量&#xff0c;本期&#xff0c;我们要分享的应用是大型工程机械3D扫描案例。 铣轮是深基础施工领域内工法先进、技术复杂程度高、高附加值的地连墙设备&#xff0c;具有成…...

使用香橙派学习 Linux的守护进程

Q&#xff1a;什么是守护进程 A&#xff1a;Linux Daemon&#xff08;守护进程&#xff09;是运行在后台的一种特殊进程。它独立于控制终端并且周期性地执行 某种任务或等待处理某些发生的事件。它不需要用户输入就能运行而且提供某种服务&#xff0c;不是对整个系统就是对某个…...

数据治理-数据仓库和商务智能

数据仓库的作用 减少数据冗余&#xff0c;提高信息一致性&#xff0c;让企业能够利用数据做出更优决策的方法&#xff0c;数据仓库是企业数据管理的核心。 业务驱动因素 运营支持职能、合规需求&#xff08;历史数据响应&#xff09;和商务智能活动&#xff08;主因&#xff1…...

CH2--x86系统架构概览

2.1 OVERVIEW OF THE SYSTEM-LEVEL ARCHITECTURE 图中的实线箭头表示线性地址&#xff0c;虚线表示段选择器&#xff0c;虚线箭头表示物理地址 2.1.1 Global and Local Descriptor Tables 全局描述符表 (GDT) GDT是一个全局的段描述符表&#xff0c;它存储在系统内存中的一个固…...

Immutable.js API 简介

Immutable-js 这个库的实现是深拷贝还是浅拷贝&#xff1f;immutable 来源immutable.js三大特性&#xff1a; 持久化数据结构结构共享惰性操作 Immutable.js 的几种数据类型 immutable 使用 使用 npm 安装 immutable&#xff1a; 常用API介绍 MapListList.isList() 和 Map.isMa…...

HLSL 入门(一)

HLSL High Level Shader Language 高级着色语言&#xff0c;是Direct3D中用来编写Shader的语言。其语法类似于C语言。 虽然其主要作用是用来编写例如顶点着色器&#xff0c;像素着色器。但本质是对图形并行管线进行编程&#xff0c;因此也能用来编写用于计算的着色器&#xff…...

【Docker】挂载数据卷

一、Docker数据卷说明及操作 在Docker中挂载数据卷是一种将数据持久化保存的方法&#xff0c;以便容器之间或容器与主机之间共享数据。以下是如何在Docker中挂载数据卷的步骤&#xff1a; 1、创建数据卷 首先&#xff0c;您需要创建一个数据卷。可以使用以下命令创建一个数据卷…...

[技术干货]spring 和spring boot区别

Spring 和 Spring Boot 都是 Java 框架&#xff0c;用于构建企业级应用程序。Spring 是一个完整的框架&#xff0c;提供各种功能&#xff0c;包括依赖注入、事务管理、数据访问、Web 开发等。Spring Boot 是一个基于 Spring 的框架&#xff0c;旨在简化 Spring 应用程序的开发和…...

【hudi】数据湖客户端运维工具Hudi-Cli实战

数据湖客户端运维工具Hudi-Cli实战 help hudi:student_mysql_cdc_hudi_fl->help AVAILABLE COMMANDSArchived Commits Commandtrigger archival: trigger archivalshow archived commits: Read commits from archived files and show detailsshow archived commit stats: …...

RK3588 添加ROOT权限

一.ROOT简介 ROOT权限是Linux和Unix系统中的超级管理员用户帐户&#xff0c;该帐户拥有整个系统的最高权利&#xff0c;可以执行几乎所有操作。ROOT就是获取安卓系统中的最高用户权限&#xff0c;以便执行一些需要高权限才能执行的操作(包括卸载系统自带程序、刷机、备份、还原…...

【云原生】k8s-----集群调度

目录 1.k8s的list-watch机制 1.1 list-watc机制简介 1.2 根据list-watch机制&#xff0c;pod的创建流程 2.scheduler的调度策略 2.1 scheduler的调度策略简介 2.2 Scheduler预选策略的算法 2.3 Scheduler优选策略的算法 3. k8s中的标签管理及nodeSelector和nodeName的 调…...

一键集成prometheus监控微服务接口平均响应时长

一、效果展示 二、环境准备 prometheus + grafana环境 参考博文:https://blog.csdn.net/luckywuxn/article/details/129475991 三、导入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter...

2023/9/13 -- C++/QT

作业&#xff1a; 1> 将之前定义的栈类和队列类都实现成模板类 栈&#xff1a; #include <iostream> #define MAX 40 using namespace std;template <typename T> class Stack{ private:T *data;int top; public:Stack();~Stack();Stack(const Stack &ot…...

mybatis mapper.xml转建表语句

从网上下载了代码&#xff0c;但是发现没有DDL建表语句&#xff0c;只能自己手动创建了&#xff0c;感觉太麻烦&#xff0c;就写了一个工具类 将所有的mapper.xml放入到一个文件夹中&#xff0c;程序会自动读取生成建表语句 依赖的jar <dependency><groupId>org.d…...

封装使用Axios进行前后端交互

Axios是一个强大的HTTP客户端&#xff0c;用于在Vue.js应用中进行前后端数据交互。本文将介绍如何在Vue中使用Axios&#xff0c;并通过一个企业应用场景来演示其实际应用。 Axios简介 公众号&#xff1a;Code程序人生&#xff0c;个人网站&#xff1a;https://creatorblog.cn A…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...