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

LeetCode-72. 编辑距离【字符串 动态规划】

LeetCode-72. 编辑距离【字符串 动态规划】

  • 题目描述:
  • 解题思路一:动规五部曲
  • 解题思路二:动态规划【版本二】
  • 解题思路三:0

题目描述:

给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

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

示例 1:

输入:word1 = “horse”, word2 = “ros”
输出:3
解释:
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)
示例 2:

输入:word1 = “intention”, word2 = “execution”
输出:5
解释:
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)

提示:

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

此题的解题思路与LeetCode-1143. 最长公共子序列【字符串 动态规划】非常一致!

解题思路一:动规五部曲

  1. 确定dp数组(dp table)以及下标的含义
    dp[i][j] 表示以下标i-1为结尾的字符串word1,和以下标j-1为结尾的字符串word2,最近编辑距离为dp[i][j]。

有同学问了,为啥要表示下标i-1为结尾的字符串呢,为啥不表示下标i为结尾的字符串呢?

为什么这么定义我在 718. 最长重复子数组 (opens new window)中做了详细的讲解。

其实用i来表示也可以! 用i-1就是为了方便后面dp数组初始化的。

  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;
}
  1. dp数组如何初始化
    再回顾一下dp[i][j]的定义:

dp[i][j] 表示以下标i-1为结尾的字符串word1,和以下标j-1为结尾的字符串word2,最近编辑距离为dp[i][j]。

那么dp[i][0] 和 dp[0][j] 表示什么呢?

dp[i][0] :以下标i-1为结尾的字符串word1,和空字符串word2,最近编辑距离为dp[i][0]。

那么dp[i][0]就应该是i,对word1里的元素全部做删除操作,即:dp[i][0] = i;

同理dp[0][j] = j;

  1. 确定遍历顺序
    从如下四个递推公式:

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矩阵中一定是从左到右从上到下去遍历。

  1. 举例推导dp数组
    以示例1为例,输入:word1 = “horse”, word2 = "ros"为例,dp矩阵状态图如下:
    在这里插入图片描述
class Solution:def minDistance(self, word1: str, word2: str) -> int:dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)]for i in range(len(word1)+1):dp[i][0] = ifor j in range(len(word2)+1):dp[0][j] = jfor i in range(1, len(word1)+1):for j in range(1, len(word2)+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]) + 1return dp[-1][-1]

时间复杂度:O(nm)
空间复杂度:O(nm)

解题思路二:动态规划【版本二】

class Solution:def minDistance(self, word1: str, word2: str) -> int:m, n = len(word1), len(word2)dp = [[0] * (n+1) for _ in range(m+1)]for i in range(m+1):dp[i][0] = ifor j in range(n+1):dp[0][j] = jfor i in range(1, m+1):for j in range(1, n+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], dp[i-1][j-1], dp[i][j-1]) + 1return dp[-1][-1]

时间复杂度:O(nm)
空间复杂度:O(nm)

解题思路三:0


时间复杂度:O(n)
空间复杂度:O(n)

相关文章:

LeetCode-72. 编辑距离【字符串 动态规划】

LeetCode-72. 编辑距离【字符串 动态规划】 题目描述&#xff1a;解题思路一&#xff1a;动规五部曲解题思路二&#xff1a;动态规划【版本二】解题思路三&#xff1a;0 题目描述&#xff1a; 给你两个单词 word1 和 word2&#xff0c; 请返回将 word1 转换成 word2 所使用的最…...

多张静图合成gif怎么做?一键极速合成gif

图片的格式有很多种&#xff0c;通常分为静态图片和动态图片。而动态图片基本上都是gif格式&#xff0c;想要把其他格式的静图变成gif格式动图的时候要怎么操作呢&#xff1f;通过使用gif动画图片&#xff08;https://www.gif.cn/&#xff09;制作网站&#xff0c;上传jpg、png…...

Es中bool 查询中的四个(must must_not should filter)

1.must :相当于and 2.must_not :相当于not 3.should:相当于or 4. filter:过滤 gte 大于 gt大于 lte小于等于 lt小于 使用示例&#xff1a; {“bool”:{“must”:{“match”:{“title”:”how to make millons “}},“must_not”:{“match”:{“tag”:”spam“}},“should”:[{…...

Docker容器嵌入式开发:Docker Ubuntu18.04配置mysql数据库

在 Ubuntu 18.04 操作系统中安装 MySQL 数据库的过程。下面是安装过程的详细描述&#xff1a; 首先&#xff0c;使用以下命令安装 MySQL 服务器&#xff1a; sudo apt install mysql-server系统会提示是否继续安装&#xff0c;按下 Y 键确认。 安装过程中&#xff0c;系统会…...

C++类和对象中上篇

1.类的6个默认成员函数 如果一个类中什么成员都没有&#xff0c;那就简称他为空类。 空类中真的什么都没有吗&#xff1f;并不是&#xff0c;任何类在什么都不写时&#xff0c;编译器会自动生成以下6个默认成员函数。 默认成员函数&#xff1a;用户没有显式实现&#xff0c;…...

基于linux进一步理解核间通讯

芯片架构分为同构和异构: 如下图TC397: 如下图TDA4: 如下图STM32MP157: 非对称多处理结构(AMP): AMP 结构是指每个内核运行自己的 OS 或同一 OS 的独立实例&#...

应用实战|从头开始开发记账本2:基于模板快速开始

上期视频我们创建好了BaaS服务的后端应用。从这期视频开始&#xff0c;我们将从头开发一个互联网记账本应用。本期视频我们介绍一下如何使用模板快速开启我们的应用开发之旅。 应用实战&#xff5c;从头开始开发记账本2&#xff1a;基于模板快速开始 相关代码 本期视频我们介绍…...

学习前端第二十天(条件分支:if 和 ‘?‘;逻辑运算符)

一、条件分支 if (…) 语句会计算圆括号内的表达式&#xff0c;并将计算结果转换为布尔型。 if(...) 语句计算括号里的条件表达式&#xff0c;如果计算结果是 true&#xff0c;就会执行对应的代码块{ }。 if 语句有时会包含一个可选的 “else” 块。如果判断条件不成立&…...

C++11的更新介绍(lamada、包装器)

&#x1fa90;&#x1fa90;&#x1fa90;欢迎来到程序员餐厅&#x1f4ab;&#x1f4ab;&#x1f4ab; 主厨&#xff1a;邪王真眼 主厨的主页&#xff1a;Chef‘s blog 所属专栏&#xff1a;c大冒险 总有光环在陨落&#xff0c;总有新星在闪烁 lambda表达式 C98中的一个…...

Golang 实现一个简单的 RPC 服务

分享一个简单的 rpc 服务框架 一、服务端实现 package mainimport ("log""net""net/rpc" )const HelloServiceName "main.HelloService"type HelloServiceInterface interface {Hello(request string, replay *string) error }func…...

Linux系统(centos,redhat,龙芯,麒麟等)忘记密码,怎么设置新的密码

Linux系统&#xff08;centos,redhat,龙芯&#xff0c;麒麟等&#xff09;忘记密码&#xff0c;怎么设置新的密码 今天在操作服务器时&#xff0c;DBA忘记了人大金仓数据库的kingbase密码&#xff0c;他的密码试了好多遍&#xff0c;都不行。最后只能给重置密码了 解决办法&a…...

SpringBoot的启动原理

运行Main方法&#xff1a; 应用程序启动始于Main方法的执行。在Main方法中&#xff0c;创建了一个SpringApplication实例&#xff0c;用于引导应用程序的启动。同时&#xff0c;SpringApplication会根据spring.factories文件加载并注册监听器、ApplicationContextInitializer等…...

git查看单独某一个文件的历史修改记录

git查看单独某一个文件的历史修改记录 git log -p 文件具体路径 注意&#xff0c;Windows下默认文件路径分隔符是 \&#xff0c;在git bash 里面需要改成 /。 git基于change代码修改与提交_git change-CSDN博客文章浏览阅读361次。git cherry-pick&#xff1a;复制多个提交comm…...

一键开启Scrum回顾会议的精彩时刻

其实回顾会议作为一个检视、反馈、改进环节&#xff0c;不仅在传统的瀑布管理模式中&#xff0c;还是在Scrum一类的敏捷管理流程中&#xff0c;都是非常重要的活动。一些团队认为它无法产生直接的价值&#xff0c;所以有意忽略了这个会议&#xff1b;一些团队在越来越多的回顾中…...

Python计算多个表格中多列数据的平均值与标准差并导出为新的Excel文件

本文介绍基于Python语言&#xff0c;对一个或多个表格文件中多列数据分别计算平均值与标准差&#xff0c;随后将多列数据对应的这2个数据结果导出为新的表格文件的方法。 首先&#xff0c;来看一下本文的需求。现有2个.csv格式的表格文件&#xff0c;其每1列表示1个变量&#x…...

nginx支持的多种负载均衡策略

目录 1.轮询&#xff08;默认&#xff09; 2. ip_hash 3. 加权轮询&#xff08;weight&#xff09; 4. fair&#xff08;第三方&#xff09; 5. 最少连接&#xff08;least_conn&#xff09; 1.轮询&#xff08;默认&#xff09; 将请求依次分配给每个服务器&#xff0c;确…...

FNP preptool has not been run on this executable

pycharm导入arcgis pro的python运行程序后提示 我也看了很多解决方法&#xff0c;也重新安装过一遍&#xff0c;终于看到一个说法是你的arcgis pro是学习版所以才会有这个提示&#xff0c;不会影响输入 测试代码 import arcpy print(arcpy.GetInstallInfo()[Version])输出结果…...

算法-反转单向链表

需求 思路 链表必有节点&#xff0c;节点两要素&#xff1a;当前元素值&#xff0c;下一个节点地址 import java.util.Scanner;// 定义一个单向链表 public class MyLinkedList<E> {int size 0;// 顶一个私有的内部类&#xff0c;表示链表的节点public class Node {E da…...

Ps 滤镜:方框模糊

Ps菜单&#xff1a;滤镜/模糊/方框模糊 Filter/Blur/Box Blur 方框模糊 Box Blur滤镜通过计算图像中每个像素及其周围像素的平均颜色值来实现模糊效果。适合于需要突出主题、减少背景&#xff08;尤其是颜色变化&#xff09;干扰的场景。 “方框模糊”滤镜按照设定的半径值&…...

MTK Android13 霸屏实现

一、背景 在台式POS场景下&#xff0c;经常有应用会需要获取霸屏的权限&#xff0c;隐藏状态栏或者导航栏&#xff0c;且不能被划出&#xff0c;其实系统已经系统了隐藏状态栏也导航栏的接口&#xff0c;但是无法做到禁止滑出。 View decorView ((Activity) context).getWin…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...