每天一道leetcode:72. 编辑距离(动态规划困难)
今日份题目:
给你两个单词 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由小写英文字母组成
题目思路
动态规划,将整个单词的编辑问题转换成三个子问题的编辑问题。
思路:插入、删除、替换三个操作可以在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. 编辑距离(动态规划困难)
今日份题目: 给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字符 替换一个字符 示例1 输入:word1 "horse", word…...
详细介绍如何使用 OpenCV 对图像进行锐化
将了解锐化图像的过程,我们将使用内核来突出显示每个特定像素并增强其发出的颜色。它与模糊过程非常相似,只不过现在我们不是创建一个内核来平均每个像素强度,而是创建一个内核,该内核将使像素强度更高,因此对人眼来说更加突出。 了解流程的后端。 很高兴知道内核用于模糊…...
Java代理模式——静态代理与动态代理
代理模式 代理模式允许你为其他对象提供一个代理,以控制对这个对象的访问。代理模式在不改变实际对象的情况下,可以在访问对象时添加额外的功能。 可以理解为代理模式为被代理对象创造了一个替身,调用者可以通过这个替身去实现这个被代理对…...
Vue day02 Computed和Watch
1.事件绑定 可以用 v-on 指令监听DOM 事件,并在触发时运行一些 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个面试题(字符串包含问题) 1丶判定是否互为字符重排 这个题我们用一个非常简单的思想就能实现,我们先将字符串转换为字符数组,然后对字符数组进行排序,然后再…...
全面掌握 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 **按↑(Up)键** keyup.up**按↓(Down)键** keyup…...
Chrome 手动代理设置 HTTP/Socks5
1、安装代理插件:SwitchyOmega 在线安装 从 Chrome 应用商店 安装,如果您无法从该链接安装,请使用下面的离线安装。 离线安装 ①、去 Github 下载 最新版安装包 ,或者直接 本地下载 文件进行安装。 ②、下载安装文件后…...
SpringBoot第35讲:SpringBoot集成连接池 - 默认连接池HikariCP
SpringBoot第35讲:SpringBoot集成连接池 - 默认连接池HikariCP 本文是SpringBoot第35讲,主要介绍数据库连接池,以及SpringBoot集成默认的HikariCP的实践。 文章目录 SpringBoot第35讲:SpringBoot集成连接池 - 默认连接池HikariCP1…...
选择最适合自己的笔记本
选择最适合自己的笔记本电脑 一、了解笔记本品牌一线品牌准一线品牌二线品牌三线品牌 二、笔记本入手渠道笔记本入手渠道 三、根据需求选择机型使用需求1.日常使用2.商务办公、财务3.轻度剪辑、ps4.代码5.创意设计6.游戏 四、笔记本电脑配置如何选1.cpu2.显卡(GPU&a…...
前端安全:探秘安全 HTTP 头的设置
在当今数字化时代,前端安全至关重要。除了应对常见的攻击方式外,通过设置安全 HTTP 头,我们可以加强网站的安全性,减少潜在的威胁。本文将为您详细解释什么是安全 HTTP 头,以及如何通过设置它们来保护您的前端应用。 1…...
python爬虫——爬虫伪装和反“反爬”
前言 爬虫伪装和反“反爬”是在爬虫领域中非常重要的话题。伪装可以让你的爬虫看起来更像普通的浏览器或者应用程序,从而减少被服务器封禁的风险;反“反爬”则是应对服务器加强的反爬虫机制。下面将详细介绍一些常见的伪装和反反爬技巧,并提…...
vue3 使用 element-china-area-data 实现地区选择器
官方地址:https://www.npmjs.com/package/element-china-area-data?activeTabreadme 在线示例:https://plortinus.github.io/element-china-area-data/index.html 实际使用 <el-col :span"12"><el-form-item label"所处城市&…...
STM32自带的DSP库的滤波初体验(一)
最近在弄STM32自带的DSP库里的滤波,记录一下: 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 中的一种特殊类型,用于表示动态的键值对数据。它可以存储任意类型的数据,并提供了方便的方法来访问和操作这些数据。 Struct 类型通常用于在不事先知道数据结构的情况下传递和处理配置、参数或其…...
Python学习笔记第五十四天(Pandas DataFrame)
Python学习笔记第五十四天 Pandas 数据结构 - DataFrame使用列表创建使用 ndarrays 创建使用字典创建返回多行数 后记 Pandas 数据结构 - DataFrame DataFrame 是一个表格型的数据结构,它含有一组有序的列,每列可以是不同的值类型(数值、字符…...
Docker镜像查看下载删除镜像文件的相关命令
1.镜像相关命令 本地查看有哪些镜像文件: docker images镜像的名称就是我们常见的一些软件,镜像相当于把软件和软件所需要的运行环境打包到一个镜像文件里面,将来在通过这个镜像文件创建出对应的容器,容器有了以后这些软件自动的…...
1. VisionOS平台介绍
介绍 VisionOS 可实现与现实世界无缝集成并与其他虚拟内容共存的 3D 多任务体验。这为个人生产力、生活方式和娱乐应用打开了一个充满新可能性的世界,并为开发人员打开了一个全新的市场。然而,它也带来了围绕多任务处理和与身体互动的新挑战。Unity Poly…...
【C#】设置有线网卡IP地址,子网掩码,网关,DNS
方法 public partial class ComputerInfo{/// <summary>/// 设置IP地址,子网掩码,网关,DNS/// </summary>public static List<NetworkAdapterInfo> SetIpAddressSubMaskDnsGeteway(string ipAddress, string subMask, stri…...
LVS-DR集群及NGINX负载均衡
LVS-DR集群 原理: 1. 当用户向负载均衡调度器(Director Server)发起请求,调度器将请求发往至内核空间 2. PREROUTING链首先会接收到用户请求,判断目标IP确定是本机IP,将数据包发往INPUT链 3. IPVS是工作在…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 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 系统…...
