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

每天一道leetcode:72. 编辑距离(动态规划困难)

今日份题目:

给你两个单词 word1word2请返回将 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

  • word1word2 由小写英文字母组成

题目思路

动态规划,将整个单词的编辑问题转换成三个子问题的编辑问题。

思路:插入、删除、替换三个操作可以在word1和word2两个单词中分别操作,并且,word1的插入操作就是word2的删除操作,同理,word2的插入操作就是word1的删除操作,所以,双方的六个操作可以简化为word1的插入操作、word2的插入操作和替换操作三个操作。假设当前位置是word1的第i个字符、word2的第j个字符。所谓word1的插入操作,就是在i-1和j的位置的基础上,也就是word1的前i-1个字符和word2的前j个字符编辑的距离的子问题下对word1进行插入操作;所谓word2的插入问题,就是在i和j-1的位置的基础上,也就是word1的前i个字符和word2的前j-1个字符编辑的距离的子问题下对word2进行插入操作;所谓替换操作,就是在i-1和j-1的位置的子问题下对当前字符进行判断是否需要替换,如果字符不同就需要替换,相同就不需要替换,注意,dp中的i是word中的i-1,因为word从0开始遍历下标,dp从1开始遍历下标。

接下来就是大家比较关心的状态转移方程问题:

根据上段的分析,我们知道,会有三种状态(三种操作对应三种状态):

//word1插入字符:word1的前i-1个字符和word2的前j个字符编辑的距离+本次word1插入1个字符
int a=dp[i-1][j]+1;
//word2插入字符:word1的前i个字符和word2的前j-1个字符编辑的距离+本次word2插入1个字符
int b=dp[i][j-1]+1;
//替换:word1的前i-1个字符和word2的前j-1个字符编辑的距离+本次替换字符
int c=dp[i-1][j-1];
if(word1[i-1]!=word2[j-1]) c+=1;
//如果word1的第i个字符(word的下标为i-1)和word2的第j个字符(word的下标为j-1)相同,就不需要进行替换修改操作

状态转移方程就是取操作后的最小状态(因为要求最小操作距离):

dp[i][j]=min(a,min(b,c));

状态转移方程对比:

最后,dp [ n ] [ m ] 就是我们要返回的答案。

这道题目比较困难,思路也可能存在漏洞,欢迎大家在评论区进行讨论,谢谢!

代码

class Solution 
{
public:int minDistance(string word1, string word2) {//获取两个字符串的长度int n=word1.length();int m=word2.length();//有一个字符串为空串if(n==0) return m;else if(m==0) return n;//dp数组int dp[1000][1000]={0};//边界状态初始化for(int i=0;i<=n;i++) {dp[i][0]=i;//相对于word1执行i次删除操作}for(int j=0;j<=m;j++) {dp[0][j]=j;//相对于word1执行j次插入操作}//计算所有dp值for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {//word1的前i-1个字符和word2的前j个字符编辑的距离+本次:word1插入1个字符int a=dp[i-1][j]+1;//word1的前i个字符和word2的前j-1个字符编辑的距离+本次:word2插入1个字符int b=dp[i][j-1]+1;//word1的前i-1个字符和word2的前j-1个字符编辑的距离+本次:替换字符int c=dp[i-1][j-1];//如果word1的第i个字符(word的下标为i-1)和word2的第j个字符(word的下标为j-1)相同,就不需要进行替换修改操作if(word1[i-1]!=word2[j-1]) c+=1;dp[i][j]=min(a,min(b,c));}}return dp[n][m];}
};

提交结果

 欢迎大家在评论区讨论,如有不懂的代码部分,欢迎在评论区留言!

相关文章:

每天一道leetcode:72. 编辑距离(动态规划困难)

今日份题目&#xff1a; 给你两个单词 word1 和 word2&#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作&#xff1a; 插入一个字符 删除一个字符 替换一个字符 示例1 输入&#xff1a;word1 "horse", word…...

详细介绍如何使用 OpenCV 对图像进行锐化

将了解锐化图像的过程,我们将使用内核来突出显示每个特定像素并增强其发出的颜色。它与模糊过程非常相似,只不过现在我们不是创建一个内核来平均每个像素强度,而是创建一个内核,该内核将使像素强度更高,因此对人眼来说更加突出。 了解流程的后端。 很高兴知道内核用于模糊…...

Java代理模式——静态代理与动态代理

代理模式 代理模式允许你为其他对象提供一个代理&#xff0c;以控制对这个对象的访问。代理模式在不改变实际对象的情况下&#xff0c;可以在访问对象时添加额外的功能。 可以理解为代理模式为被代理对象创造了一个替身&#xff0c;调用者可以通过这个替身去实现这个被代理对…...

Vue day02 Computed和Watch

1.事件绑定 可以用 v-on 指令监听DOM 事件&#xff0c;并在触发时运行一些 JavaScript 代码。v-on 还可以接收一个需要调用的方法名称。 <button v-on:click"handler">good</button> methods: { handler: function (event) { if (event) { alert(event.t…...

【Java】一只小菜坤的编程题之旅【3】

文章目录 1丶判定是否互为字符重排2、杨辉三角3丶某公司的1个面试题&#xff08;字符串包含问题&#xff09; 1丶判定是否互为字符重排 这个题我们用一个非常简单的思想就能实现&#xff0c;我们先将字符串转换为字符数组&#xff0c;然后对字符数组进行排序&#xff0c;然后再…...

全面掌握 Jaeger 分布式调用链路跟踪理论和实战,Go 为所有使用 go-resty 库发起 HTTP 请求集成链路跟踪 jaeger(附源码)

全面掌握 Jaeger 分布式调用链路跟踪理论和实战,Go 为所有使用 go-resty 库发起 HTTP 请求集成链路跟踪 jaeger(附源码)。 介绍一个开源的分布式跟踪系统 Jaeger,首先从理论基础知识开始学习,将学习如何在 HTTP 请求中集成链路跟踪,以及如何在 GORM 框架实现,最后学习 …...

vue键盘和鼠标事件

1、键盘事件 **按Enter键** keyup.enter**按PageDown键** keyup.page-down **按Tab键** keyup.tab **按Delete键** keyup.delete **按ESC键** keyup.esc**按Space键** keyup.space **按↑&#xff08;Up&#xff09;键** keyup.up**按↓&#xff08;Down&#xff09;键** keyup…...

Chrome 手动代理设置 HTTP/Socks5

1、安装代理插件&#xff1a;SwitchyOmega 在线安装 从 Chrome 应用商店 安装&#xff0c;如果您无法从该链接安装&#xff0c;请使用下面的离线安装。 离线安装 ①、去 Github 下载 最新版安装包 &#xff0c;或者直接 本地下载 文件进行安装。 ②、下载安装文件后&#xf…...

SpringBoot第35讲:SpringBoot集成连接池 - 默认连接池HikariCP

SpringBoot第35讲&#xff1a;SpringBoot集成连接池 - 默认连接池HikariCP 本文是SpringBoot第35讲&#xff0c;主要介绍数据库连接池&#xff0c;以及SpringBoot集成默认的HikariCP的实践。 文章目录 SpringBoot第35讲&#xff1a;SpringBoot集成连接池 - 默认连接池HikariCP1…...

选择最适合自己的笔记本

选择最适合自己的笔记本电脑 一、了解笔记本品牌一线品牌准一线品牌二线品牌三线品牌 二、笔记本入手渠道笔记本入手渠道 三、根据需求选择机型使用需求1.日常使用2.商务办公、财务3.轻度剪辑、ps4.代码5.创意设计6.游戏 四、笔记本电脑配置如何选1.cpu2.显卡&#xff08;GPU&a…...

前端安全:探秘安全 HTTP 头的设置

在当今数字化时代&#xff0c;前端安全至关重要。除了应对常见的攻击方式外&#xff0c;通过设置安全 HTTP 头&#xff0c;我们可以加强网站的安全性&#xff0c;减少潜在的威胁。本文将为您详细解释什么是安全 HTTP 头&#xff0c;以及如何通过设置它们来保护您的前端应用。 1…...

python爬虫——爬虫伪装和反“反爬”

前言 爬虫伪装和反“反爬”是在爬虫领域中非常重要的话题。伪装可以让你的爬虫看起来更像普通的浏览器或者应用程序&#xff0c;从而减少被服务器封禁的风险&#xff1b;反“反爬”则是应对服务器加强的反爬虫机制。下面将详细介绍一些常见的伪装和反反爬技巧&#xff0c;并提…...

vue3 使用 element-china-area-data 实现地区选择器

官方地址&#xff1a;https://www.npmjs.com/package/element-china-area-data?activeTabreadme 在线示例&#xff1a;https://plortinus.github.io/element-china-area-data/index.html 实际使用 <el-col :span"12"><el-form-item label"所处城市&…...

STM32自带的DSP库的滤波初体验(一)

最近在弄STM32自带的DSP库里的滤波&#xff0c;记录一下&#xff1a; arm_fir_instance_q15 instance_q15_S; #define NUM_TAPS 16 //滤波系数的个数 #define BLOCK_SIZE 32 q15_t firStateF32[BLOCK_SIZE NUM_TAPS]; q15_t Fir_Coeff[NUM_TAPS] {-79, -136, 312, 6…...

go kratos protobuf 接收动态JSON数据

前言 google.protobuf.Struct 是 Google Protocol Buffers 中的一种特殊类型&#xff0c;用于表示动态的键值对数据。它可以存储任意类型的数据&#xff0c;并提供了方便的方法来访问和操作这些数据。 Struct 类型通常用于在不事先知道数据结构的情况下传递和处理配置、参数或其…...

Python学习笔记第五十四天(Pandas DataFrame)

Python学习笔记第五十四天 Pandas 数据结构 - DataFrame使用列表创建使用 ndarrays 创建使用字典创建返回多行数 后记 Pandas 数据结构 - DataFrame DataFrame 是一个表格型的数据结构&#xff0c;它含有一组有序的列&#xff0c;每列可以是不同的值类型&#xff08;数值、字符…...

Docker镜像查看下载删除镜像文件的相关命令

1.镜像相关命令 本地查看有哪些镜像文件&#xff1a; docker images镜像的名称就是我们常见的一些软件&#xff0c;镜像相当于把软件和软件所需要的运行环境打包到一个镜像文件里面&#xff0c;将来在通过这个镜像文件创建出对应的容器&#xff0c;容器有了以后这些软件自动的…...

1. VisionOS平台介绍

介绍 VisionOS 可实现与现实世界无缝集成并与其他虚拟内容共存的 3D 多任务体验。这为个人生产力、生活方式和娱乐应用打开了一个充满新可能性的世界&#xff0c;并为开发人员打开了一个全新的市场。然而&#xff0c;它也带来了围绕多任务处理和与身体互动的新挑战。Unity Poly…...

【C#】设置有线网卡IP地址,子网掩码,网关,DNS

方法 public partial class ComputerInfo{/// <summary>/// 设置IP地址&#xff0c;子网掩码&#xff0c;网关&#xff0c;DNS/// </summary>public static List<NetworkAdapterInfo> SetIpAddressSubMaskDnsGeteway(string ipAddress, string subMask, stri…...

LVS-DR集群及NGINX负载均衡

LVS-DR集群 原理&#xff1a; 1. 当用户向负载均衡调度器&#xff08;Director Server&#xff09;发起请求&#xff0c;调度器将请求发往至内核空间 2. PREROUTING链首先会接收到用户请求&#xff0c;判断目标IP确定是本机IP&#xff0c;将数据包发往INPUT链 3. IPVS是工作在…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...