每天一道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是工作在…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
