当前位置: 首页 > 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…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...