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. 编辑距离(动态规划)
题目: 链接:LeetCode 72. 编辑距离 难度:中等 给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符删除一个字符替换一个字符 示例…...
Bytedance揭秘OpenAI大模型: GPT-3到GPT-4进化路径
文章目录 探秘GPT-3到GPT-4进化之路1、SFT:早期GPT进化的推动者2、RLHF和SFT:编码能力提升的功臣3、代码加入预训练,对推理帮助最大4、“跷跷板”现象 论文地址项目链接Reference GPT-Fathom: Benchmarking Large Language Models to Deciphe…...
第二十六章 BEV感知系列三(车道线感知)
前言 近期参与到了手写AI的车道线检测的学习中去,以此系列笔记记录学习与思考的全过程。车道线检测系列会持续更新,力求完整精炼,引人启示。所需前期知识,可以结合手写AI进行系统的学习。 BEV感知系列是对论文Delving into the De…...
总结几个面试题
目录 1. this 指针存在哪里 2. this指针可以为空吗? 3. 结构体怎么对齐?为什么要进行内存对齐? 4. 如何让结构体按照指定的对齐方式对齐?能否按照3、4、5即任意字节对齐? 5. 什么是大小端?如何测…...
【多线程】并发问题
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工具类的问题: 1.1、如下图我们都能够发现这种封装的问题: 代码繁杂、充斥了很多重复性代码返回值单一,无法拿到对应的Java Bean对象及List对象集合实际场景中会对接大量第三方的OPEN API,下述方法的扩展…...
【华为OD题库-003】最佳植树距离-Java
题目 小明在直线的公路上种树,现在给定可以种树的坑位的数星和位置,以及需要种多少棵树苗,问树苗之间的最小间距是多少时,可以保证种的最均匀(两棵树苗之间的最小间距最大) 输入描述 输入三行: 第一行一个整数:坑位的数…...
Oracle(12)Managing Indexes
目录 目标: 一、基础知识 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文件代码着色器文件代码 效果展示 任务要求 本篇文章是中国农业大学虚拟现实课程的一次作业内容,需要对五个茶壶模型使用不同的光照进行着色和渲染,然后旋转展示。 本人的代码也是在其他人的代码的基础上修改来的…...
【Verilog 教程】7.3 Verilog 串行 FIR 滤波器设计
串行 FIR 滤波器设计 设计说明 设计参数不变,与并行 FIR 滤波器参数一致。即,输入频率为 7.5 MHz 和 250 KHz 的正弦波混合信号,经过 FIR 滤波器后,高频信号 7.5MHz 被滤除,只保留 250KMHz 的信号。 输入频率&#x…...
用golang实现一个基于interface的多态示例,展示其使用场景和优劣性。
以下是一个简单的基于interface的多态示例,该示例展示了如何通过使用interface来实现多个不同类型的结构体的共同行为。具体示例如下: package mainimport "fmt"type Animal interface {Speak() string }type Dog struct {Name string }func …...
ArcGIS for Android 禁止地图旋转
ArcGIS for Android 禁止地图旋转 话不多说,直接上代码!!! public class LoadMap extends AppCompatActivity {// 地图private MapView mapView;private ArcGISMap map;Overrideprotected void onCreate(Bundle savedInstanceSta…...
freertos静态创建任务
在开始前先有个小插曲,我的keil的自动补全代码功能使用不了,经过查找是因为之前装51把有的文件覆盖了,照这篇博客就可以解决。 然后之前那份代码我们是动态创建任务,先来说一下动态创建任务和静态创建任务的区别: Fre…...
VBA根据Excel内容快速创建PPT
示例需求:根据Excel中选中的单元格内容(3列)如下图所示,在已打卡的PowerPoint文件中创建页面。 新增PPT Slide页面使用第二个模板页面,其中包含两个文本占位符,和一个图片占位符。将Excel选中区域中前两列写…...
服务器操作系统有哪些
服务器操作系统有哪些 电脑想要运行就离不开操作系统,而服务器想要正常运行同样也离不开操作系统,那你知道服务器系统有哪些?服务器系统与电脑系统有什么区别?这些问题就由壹基比小鑫在下文中来告诉大家。 服务器系统有哪些&…...
泄漏检测与修复(LDAR)过程管控平台(销售出租)VOCs便携式总烃分析仪(销售出租)
LDAR是Leak Detection and Repair(泄漏检测与修复)的缩写,也是国际上较先进的化工废气检测技术。LDAR主要通过检测化工企业原料输送管道、泵、阀门、法兰等易产生易产生挥发性有机物(简称VOCs)泄漏的部位,并…...
VueX 模块化和namespace
当我们的项目很大的时候,VueX中的代码会越来越多,会有处理数据的,处理人员列表的,处理订单的... 如果我们将这些东西都写在一个state、actions和mutations中的话,就非常不方便后期的维护。 所以我们引入了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; 使用官方的这个: vite.config.js中配置 plugins: [vue(),AutoImport({resolvers: [ElementPlusResolve…...
[LeetCode]-876.链表的中间结点-206.反转链表-21.合并两个有序链表-203.移除链表元素
目录 876.链表的中间结点 题目 思路 代码 206.反转链表 题目 思路 代码 21.合并两个有序链表 题目 思路 代码 203.移除链表元素 题目 思路 代码 876.链表的中间结点 876. 链表的中间结点 - 力扣(LeetCode)https://leetcode.cn/problems/mi…...
毛发质感始终“塑料感”?5类生物毛发纹理映射表,含真实显微扫描数据+对应--s、--style、--stylize配置
更多请点击: https://codechina.net 第一章:毛发质感生成的核心困境与突破路径 毛发渲染在影视特效、实时游戏与数字人建模中长期面临物理真实性与计算效率的双重挑战。其核心困境源于微观几何结构的多尺度耦合特性——单根毛发具有弯曲、扭转、分叉、鳞…...
百度文库文档免费下载终极指南:三步获取PDF完整教程
百度文库文档免费下载终极指南:三步获取PDF完整教程 【免费下载链接】baidu-wenku fetch the document for free 项目地址: https://gitcode.com/gh_mirrors/ba/baidu-wenku 你是否经常在百度文库找到心仪的文档,却因为需要下载券或付费而无法保存…...
PPTist:重新定义在线演示文稿创作的Web应用革命
PPTist:重新定义在线演示文稿创作的Web应用革命 【免费下载链接】PPTist PowerPoint-ist(/pauəpɔintist/), An online presentation application that replicates most of the commonly used features of MS PowerPoint, allowing for the …...
DistroAV(原OBS-NDI)完整使用指南:NDI技术在OBS中的高效应用
DistroAV(原OBS-NDI)完整使用指南:NDI技术在OBS中的高效应用 【免费下载链接】obs-ndi DistroAV (formerly OBS-NDI): NDI integration for OBS Studio 项目地址: https://gitcode.com/gh_mirrors/ob/obs-ndi DistroAV(原名…...
提升3倍效率的Windows桌面端酷安社区解决方案:基于UWP平台的高性能第三方客户端
提升3倍效率的Windows桌面端酷安社区解决方案:基于UWP平台的高性能第三方客户端 【免费下载链接】Coolapk-UWP 一个基于 UWP 平台的第三方酷安客户端 项目地址: https://gitcode.com/gh_mirrors/co/Coolapk-UWP Coolapk-UWP是一款基于UWP平台的第三方酷安客户…...
Camunda流程版本管理避坑指南:从Version Tag查询到迁移验证,这些细节决定成败
Camunda流程版本管理实战精要:从精准查询到安全迁移的全链路策略 在企业级流程自动化领域,Camunda作为领先的工作流引擎,其版本管理机制直接影响着业务系统的稳定性和迭代效率。本文将深入剖析版本管理的核心痛点,提供一套覆盖全…...
用一台旧笔记本和朋友联机玩《我的世界》Fear Nightfall整合包,保姆级开服教程(含SakuraFrp配置)
用旧笔记本搭建《我的世界》Fear Nightfall联机服务器的完整指南 1. 为什么选择旧笔记本作为服务器主机? 对于许多《我的世界》玩家来说,和朋友一起体验大型整合包是件令人兴奋的事,但租用云服务器的高昂成本往往让人望而却步。实际上&…...
Miniconda虚拟环境配置踩坑实录:从‘CondaHTTPError’到完美隔离环境
Miniconda虚拟环境配置踩坑实录:从‘CondaHTTPError’到完美隔离环境 第一次在终端输入conda create -n myenv python3.8时,满心期待能快速搭建起一个干净的Python工作环境。然而几秒钟后,屏幕上突然跳出的红色报错信息让整个流程戛然而止&a…...
如何快速实现碧蓝航线全自动托管:智能脚本Alas终极指南
如何快速实现碧蓝航线全自动托管:智能脚本Alas终极指南 【免费下载链接】AzurLaneAutoScript Azur Lane bot (CN/EN/JP/TW) 碧蓝航线脚本 | 无缝委托科研,全自动大世界 项目地址: https://gitcode.com/gh_mirrors/az/AzurLaneAutoScript 还在为碧…...
Fansly下载器完整指南:3分钟掌握免费离线下载技巧
Fansly下载器完整指南:3分钟掌握免费离线下载技巧 【免费下载链接】fansly-downloader Easy to use fansly.com content downloading tool. Written in python, but ships as a standalone Executable App for Windows too. Enjoy your Fansly content offline anyt…...
