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…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
