代码随想录算法训练营第56天 | ● 583. 两个字符串的删除操作 ● 72. 编辑距离 ● 动态规划之编辑距离总结篇
文章目录
- 前言
- 一、583. 两个字符串的删除操作
- 二、72. 编辑距离
- 三、动态规划之编辑距离总结篇
- 总结
前言
一、583. 两个字符串的删除操作
两种思路:1.直接动态规划,求两个字符串需要删除的最小次数 2.采用子序列的和-最长公共子序列。思路一分析如下:
动规五部曲,分析如下:
- 确定dp数组(dp table)以及下标的含义
dp[i][j]:以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等,所需要删除元素的最少次数。
这里dp数组的定义有点点绕,大家要撸清思路。
- 确定递推公式
- 当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。
- dp数组如何初始化
从递推公式中,可以看出来,dp[i][0] 和 dp[0][j]是一定要初始化的。
dp[i][0]:word2为空字符串,以i-1为结尾的字符串word1要删除多少个元素,才能和word2相同呢,很明显dp[i][0] = i。
- 确定遍历顺序
从递推公式 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]可以根据之前计算出来的数值进行计算。
- 举例推导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. 两个字符串的删除操作 两种思路:1.直接动态规划,求两个字符串需要删除的最小次数 2.采用子序列的和-最长公共子序列。思路一分析如下&#…...
矩阵 m * M = c
文章目录 题1题2 题1 (2023江苏领航杯-prng) 题目来源: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/ 题目描述: (没有原数据,自己生成的数据) from Crypto.Util.number…...

Linux——IO
✅<1>主页::我的代码爱吃辣 📃<2>知识讲解:Linux——文件系统 ☂️<3>开发环境:Centos7 💬<4>前言:是不是只有C/C有文件操作呢?python,java&…...

svn(乌龟svn)和SVN-VS2022插件(visualsvn) 下载
下载地址: https://www.visualsvn.com/visualsvn/download/...

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

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

使用香橙派学习 Linux的守护进程
Q:什么是守护进程 A:Linux Daemon(守护进程)是运行在后台的一种特殊进程。它独立于控制终端并且周期性地执行 某种任务或等待处理某些发生的事件。它不需要用户输入就能运行而且提供某种服务,不是对整个系统就是对某个…...
数据治理-数据仓库和商务智能
数据仓库的作用 减少数据冗余,提高信息一致性,让企业能够利用数据做出更优决策的方法,数据仓库是企业数据管理的核心。 业务驱动因素 运营支持职能、合规需求(历史数据响应)和商务智能活动(主因࿱…...

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

Immutable.js API 简介
Immutable-js 这个库的实现是深拷贝还是浅拷贝?immutable 来源immutable.js三大特性: 持久化数据结构结构共享惰性操作 Immutable.js 的几种数据类型 immutable 使用 使用 npm 安装 immutable: 常用API介绍 MapListList.isList() 和 Map.isMa…...
HLSL 入门(一)
HLSL High Level Shader Language 高级着色语言,是Direct3D中用来编写Shader的语言。其语法类似于C语言。 虽然其主要作用是用来编写例如顶点着色器,像素着色器。但本质是对图形并行管线进行编程,因此也能用来编写用于计算的着色器ÿ…...
【Docker】挂载数据卷
一、Docker数据卷说明及操作 在Docker中挂载数据卷是一种将数据持久化保存的方法,以便容器之间或容器与主机之间共享数据。以下是如何在Docker中挂载数据卷的步骤: 1、创建数据卷 首先,您需要创建一个数据卷。可以使用以下命令创建一个数据卷…...
[技术干货]spring 和spring boot区别
Spring 和 Spring Boot 都是 Java 框架,用于构建企业级应用程序。Spring 是一个完整的框架,提供各种功能,包括依赖注入、事务管理、数据访问、Web 开发等。Spring Boot 是一个基于 Spring 的框架,旨在简化 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系统中的超级管理员用户帐户,该帐户拥有整个系统的最高权利,可以执行几乎所有操作。ROOT就是获取安卓系统中的最高用户权限,以便执行一些需要高权限才能执行的操作(包括卸载系统自带程序、刷机、备份、还原…...

【云原生】k8s-----集群调度
目录 1.k8s的list-watch机制 1.1 list-watc机制简介 1.2 根据list-watch机制,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
作业: 1> 将之前定义的栈类和队列类都实现成模板类 栈: #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转建表语句
从网上下载了代码,但是发现没有DDL建表语句,只能自己手动创建了,感觉太麻烦,就写了一个工具类 将所有的mapper.xml放入到一个文件夹中,程序会自动读取生成建表语句 依赖的jar <dependency><groupId>org.d…...
封装使用Axios进行前后端交互
Axios是一个强大的HTTP客户端,用于在Vue.js应用中进行前后端数据交互。本文将介绍如何在Vue中使用Axios,并通过一个企业应用场景来演示其实际应用。 Axios简介 公众号:Code程序人生,个人网站:https://creatorblog.cn A…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...

Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...

cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...

IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...