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

LeetCode 72. 编辑距离(动态规划)

题目:

链接: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 由小写英文字母组成

解题思路:

详见《Hello 算法》:编辑距离问题

代码:

class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size();int m = word2.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1));for (int i = 1; i <= n; i++) dp[i][0] = i; // 插入n个字符的操作数for (int j = 1; j <= m; j++) dp[0][j] = j;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (word1[i - 1] != word2[j - 1]) {dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; // 对应插入、删除、替换三种操作} else {dp[i][j] = dp[i - 1][j - 1]; // 相同字符不需要操作}}}return dp[n][m];}
};

时间复杂度O(NM),空间复杂度O(NM)。N、M为字符串 word1 和 word2 的长度。

相关文章:

LeetCode 72. 编辑距离(动态规划)

题目&#xff1a; 链接&#xff1a;LeetCode 72. 编辑距离 难度&#xff1a;中等 给你两个单词 word1 和 word2&#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作&#xff1a; 插入一个字符删除一个字符替换一个字符 示例…...

Bytedance揭秘OpenAI大模型: GPT-3到GPT-4进化路径

文章目录 探秘GPT-3到GPT-4进化之路1、SFT&#xff1a;早期GPT进化的推动者2、RLHF和SFT&#xff1a;编码能力提升的功臣3、代码加入预训练&#xff0c;对推理帮助最大4、“跷跷板”现象 论文地址项目链接Reference GPT-Fathom: Benchmarking Large Language Models to Deciphe…...

第二十六章 BEV感知系列三(车道线感知)

前言 近期参与到了手写AI的车道线检测的学习中去&#xff0c;以此系列笔记记录学习与思考的全过程。车道线检测系列会持续更新&#xff0c;力求完整精炼&#xff0c;引人启示。所需前期知识&#xff0c;可以结合手写AI进行系统的学习。 BEV感知系列是对论文Delving into the De…...

总结几个面试题

目录 1. this 指针存在哪里 2. this指针可以为空吗&#xff1f; 3. 结构体怎么对齐&#xff1f;为什么要进行内存对齐&#xff1f; 4. 如何让结构体按照指定的对齐方式对齐&#xff1f;能否按照3、4、5即任意字节对齐&#xff1f; 5. 什么是大小端&#xff1f;如何测…...

【多线程】并发问题

public class BuyTicket implements Runnable{private int ticketNums10;Overridepublic void run() {for(int i1;i<ticketNums;i){if(ticketNums<0){break;}System.out.println(Thread.currentThread().getName() "抢到了第" i "张票");ticketNu…...

httpclient工具类(支持泛型转换)

1、网上搜到的httpclient工具类的问题&#xff1a; 1.1、如下图我们都能够发现这种封装的问题&#xff1a; 代码繁杂、充斥了很多重复性代码返回值单一&#xff0c;无法拿到对应的Java Bean对象及List对象集合实际场景中会对接大量第三方的OPEN API&#xff0c;下述方法的扩展…...

【华为OD题库-003】最佳植树距离-Java

题目 小明在直线的公路上种树&#xff0c;现在给定可以种树的坑位的数星和位置&#xff0c;以及需要种多少棵树苗&#xff0c;问树苗之间的最小间距是多少时&#xff0c;可以保证种的最均匀&#xff08;两棵树苗之间的最小间距最大) 输入描述 输入三行: 第一行一个整数:坑位的数…...

Oracle(12)Managing Indexes

目录 目标&#xff1a; 一、基础知识 1、Classification ofindexes 索引的分类 2、B-Tree vs Bitmap 3、Creating Indexes: Guidelines 创建索引:准则 4、Offline Index Rebuild 脱机索引重建 5、RebuildingIndexes 重建索引 6、Online Index Rebuild 在线索引重建 7…...

DirectX3D 虚拟现实项目 三维物体的光照及着色(五个不同着色效果的旋转茶壶)

文章目录 任务要求原始代码CPP文件代码着色器文件代码 效果展示 任务要求 本篇文章是中国农业大学虚拟现实课程的一次作业内容&#xff0c;需要对五个茶壶模型使用不同的光照进行着色和渲染&#xff0c;然后旋转展示。 本人的代码也是在其他人的代码的基础上修改来的&#xf…...

【Verilog 教程】7.3 Verilog 串行 FIR 滤波器设计

串行 FIR 滤波器设计 设计说明 设计参数不变&#xff0c;与并行 FIR 滤波器参数一致。即&#xff0c;输入频率为 7.5 MHz 和 250 KHz 的正弦波混合信号&#xff0c;经过 FIR 滤波器后&#xff0c;高频信号 7.5MHz 被滤除&#xff0c;只保留 250KMHz 的信号。 输入频率&#x…...

用golang实现一个基于interface的多态示例,展示其使用场景和优劣性。

以下是一个简单的基于interface的多态示例&#xff0c;该示例展示了如何通过使用interface来实现多个不同类型的结构体的共同行为。具体示例如下&#xff1a; package mainimport "fmt"type Animal interface {Speak() string }type Dog struct {Name string }func …...

ArcGIS for Android 禁止地图旋转

ArcGIS for Android 禁止地图旋转 话不多说&#xff0c;直接上代码&#xff01;&#xff01;&#xff01; public class LoadMap extends AppCompatActivity {// 地图private MapView mapView;private ArcGISMap map;Overrideprotected void onCreate(Bundle savedInstanceSta…...

freertos静态创建任务

在开始前先有个小插曲&#xff0c;我的keil的自动补全代码功能使用不了&#xff0c;经过查找是因为之前装51把有的文件覆盖了&#xff0c;照这篇博客就可以解决。 然后之前那份代码我们是动态创建任务&#xff0c;先来说一下动态创建任务和静态创建任务的区别&#xff1a; Fre…...

VBA根据Excel内容快速创建PPT

示例需求&#xff1a;根据Excel中选中的单元格内容&#xff08;3列&#xff09;如下图所示&#xff0c;在已打卡的PowerPoint文件中创建页面。 新增PPT Slide页面使用第二个模板页面&#xff0c;其中包含两个文本占位符&#xff0c;和一个图片占位符。将Excel选中区域中前两列写…...

服务器操作系统有哪些

服务器操作系统有哪些 电脑想要运行就离不开操作系统&#xff0c;而服务器想要正常运行同样也离不开操作系统&#xff0c;那你知道服务器系统有哪些&#xff1f;服务器系统与电脑系统有什么区别&#xff1f;这些问题就由壹基比小鑫在下文中来告诉大家。 服务器系统有哪些&…...

泄漏检测与修复(LDAR)过程管控平台(销售出租)VOCs便携式总烃分析仪(销售出租)

LDAR是Leak Detection and Repair&#xff08;泄漏检测与修复&#xff09;的缩写&#xff0c;也是国际上较先进的化工废气检测技术。LDAR主要通过检测化工企业原料输送管道、泵、阀门、法兰等易产生易产生挥发性有机物&#xff08;简称VOCs&#xff09;泄漏的部位&#xff0c;并…...

VueX 模块化和namespace

当我们的项目很大的时候&#xff0c;VueX中的代码会越来越多&#xff0c;会有处理数据的&#xff0c;处理人员列表的&#xff0c;处理订单的... 如果我们将这些东西都写在一个state、actions和mutations中的话&#xff0c;就非常不方便后期的维护。 所以我们引入了VueX的模块…...

7-4 修理牧场 分数 15

#include<iostream> #include<queue> using namespace std; #define maxn 10005int main() {int n 0, data 0;cin >> n;//建小堆: //上调建堆中用greater: 父大子小 父子交换 小的上去 大的下去 priority_queue<int, vector<int>, greater<int…...

自定义element-ui plus 函数式调用,在API,js中直接使用全局组件

npm方式: npm install -D unplugin-vue-components unplugin-auto-import yarn 方式 : yarn add unplugin-vue-components; yarn add unplugin-auto-import; 使用官方的这个&#xff1a; vite.config.js中配置 plugins: [vue(),AutoImport({resolvers: [ElementPlusResolve…...

[LeetCode]-876.链表的中间结点-206.反转链表-21.合并两个有序链表-203.移除链表元素

目录 876.链表的中间结点 题目 思路 代码 206.反转链表 题目 思路 代码 21.合并两个有序链表 题目 思路 代码 203.移除链表元素 题目 思路 代码 876.链表的中间结点 876. 链表的中间结点 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/mi…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...