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

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

动态规划

dp[i][j] 表示以下标i-1为结尾的字符串word1,和以下标j-1为结尾的字符串word2,最近编辑距离为dp[i][j]。
这样定义的目的是便于初始化数组。

增加操作:dp[i][j-1]+1
删除操作:dp[i-1][j]+1
改操作:dp[i-1][j-1]+1

当word1[i-1]==word2[j-1]时,则dp[i][j]=dp[i-1][j-1],无需操作

class Solution {
public:int dp[505][505];int minDistance(string word1, string word2) {int len1=word1.size(),len2=word2.size();//初始化数组操作for(int i=0;i<=len1;i++) dp[i][0]=i;for(int i=0;i<=len2;i++) dp[0][i]=i;for(int i=1;i<=len1;i++){for(int j=1;j<=len2;j++){if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];else dp[i][j]=min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1));}}return dp[len1][len2];}
};

相关文章:

72. 编辑距离【leetcode】/动态规划难

72. 编辑距离 给你两个单词 word1 和 word2&#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作&#xff1a; 插入一个字符删除一个字符替换一个字符 示例 1&#xff1a; 输入&#xff1a;word1 “horse”, word2 “ros”…...

【MySQL】视图、索引

目录 视图视图的用途优点视图的缺点创建视图查看视图修改视图删除视图注意事项 索引索引的原理索引的数据结构二分查找法Hash结构Hash冲突&#xff01;&#xff01;&#xff01; B树二叉查找树 存在问题改造二叉树——B树降低树的高度 B树特点案例继续优化的方向 改造B树——B树…...

反编译java生成的.class文件

java代码编译后生成xxx.class文件&#xff0c;有时候需要反编译这个class文件看代码是怎么写的&#xff0c;可以使用下面这个工具。 工具已经上传到资源&#xff0c;链接&#xff1a; https://download.csdn.net/download/weixin_42556307/88915887 具体使用如下&#xff1a; …...

Cookie 探秘:了解 Web 浏览器中的小甜饼

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…...

Python线性代数数字图像和小波分析之二

要点 数学方程&#xff1a;数字信号和傅里叶分析&#xff0c;离散时间滤波器&#xff0c;小波分析Python代码实现及应用变换过程&#xff1a; 读取音频和处理音频波&#xff0c;使用Karplus-强算法制作吉他音频离散傅里叶计算功能和绘制图示结果计算波形傅里叶系数正向和反向&…...

LC.exe”已退出,代码为 -1

尽管网络上已经有许多详尽的说明和资料&#xff0c;但鉴于个人对大量文字的理解有反感&#xff0c;我就写一个更为直观、简洁的方式来呈现我的解决方案。 1.问题图片。 2.删除licenses.licx 3.问题解决...

springboot + jpa + 达梦数据库兼容 Mysql的GenerationType.IDENTITY主键生成策略

导入达梦数据库对hibernate的方言包 <dependency><groupId>com.dameng</groupId><artifactId>DmDialect-for-hibernate5.6</artifactId><version>8.1.2.192</version></dependency>配置文件中添加方言配置和主键生成策略配置…...

Redis优化与应用

Redis性能调优 - Redis的性能调优是一个比较复杂的过程&#xff0c;需要从多个方面进行优化&#xff0c;如内存使用、命令使用等。 - 案例&#xff1a;减少不必要的持久化操作。默认情况下&#xff0c;Redis会执行RDB和AOF两种持久化方式。如果不需要持久化&#xff0c;或者可…...

深入了解Kafka的文件存储原理

Kafka简介 Kafka最初由Linkedin公司开发的分布式、分区的、多副本的、多订阅者的消息系统。它提供了类似于JMS的特性&#xff0c;但是在设计实现上完全不同&#xff0c;此外它并不是JMS规范的实现。kafka对消息保存是根据Topic进行归类&#xff0c;发送消息者称为Producer&…...

RabbitMQ 高级

在昨天的练习作业中&#xff0c;我们改造了余额支付功能&#xff0c;在支付成功后利用RabbitMQ通知交易服务&#xff0c;更新业务订单状态为已支付。 但是大家思考一下&#xff0c;如果这里MQ通知失败&#xff0c;支付服务中支付流水显示支付成功&#xff0c;而交易服务中的订单…...

音视频开发之旅——音频基础概念、交叉编译原理和实践(LAME的交叉编译)(Android)

本文主要讲解的是音频基础概念、交叉编译原理和实践&#xff08;LAME的交叉编译&#xff09;&#xff0c;是基于Android平台&#xff0c;示例代码如下所示&#xff1a; AndroidAudioDemo 音频基础概念 在进行音频开发的之前&#xff0c;了解声学的基础还是很有必要的。 声音…...

直播美颜SDK开发指南:构建个性化的主播美颜工具

本篇文章&#xff0c;小编将带您深入了解如何构建个性化的主播美颜工具&#xff0c;从而为用户提供更优质的直播体验。 一、美颜技术概述 在开始SDK的开发之前&#xff0c;我们首先需要了解美颜技术的基本原理。美颜技术通常包括肤色检测、人脸检测、特征点定位、滤镜处理等步…...

羊大师揭秘,羊奶有哪些好处和不足呢?

羊大师揭秘&#xff0c;羊奶有哪些好处和不足呢&#xff1f; 羊奶的好处主要包括&#xff1a; 营养丰富&#xff1a;羊奶中含有多种人体所需的营养成分&#xff0c;如蛋白质、脂肪、碳水化合物、矿物质和维生素等。尤其是蛋白质含量高&#xff0c;且易于人体吸收利用。 增强免…...

鸿蒙问题之CustomDialog后持久化@state数据崩溃

开发需求&#xff1a;有一个字符串数组&#xff0c;可以通过弹框编辑其中的某个字符串&#xff0c;编辑完成后更新数组并持久化这个数组。 这个需求算是很简单&#xff0c;很常见的需求了。但是&#xff0c;开发过程中却遇到了一个不小的难题。 我的数组内容需要在组件中显示…...

微服务高性能通信技术-gRPC实战落地

在微服务架构中&#xff0c;服务之间的通信是至关重要的。为了实现高性能、低延迟和跨语言的服务间通信&#xff0c;gRPC是一个流行的选择。gRPC是一个开源的、高性能的、通用的RPC&#xff08;远程过程调用&#xff09;框架&#xff0c;基于HTTP/2协议和Protocol Buffers序列化…...

洛阳旅游攻略

洛阳旅游攻略 第一天&#xff08;抵达当天&#xff09;&#xff1a; 1.先将行李放到酒店—2.老城十字街&#xff08;打车可能会堵车&#xff09;—3.洛邑古城—4.丽景门&#xff08;步行&#xff09; 第二天&#xff1a; 1.早起吃早餐—&#xff08;打车三十分钟&#xff0c…...

图论例题解析

1.图论基础概念 概念 &#xff08;注意连通非连通情况&#xff0c;1节点&#xff09; 无向图&#xff1a; 度是边的两倍&#xff08;没有入度和出度的概念&#xff09; 1.完全图&#xff1a; 假设一个图有n个节点&#xff0c;那么任意两个节点都有边则为完全图 2.连通图&…...

图解 TCP 拥塞控制

文章目录 什么是拥塞控制拥塞控制算法慢启动拥塞避免快速恢复 TCP拥塞控制状态机 什么是拥塞控制 拥塞控制是一种 确保网络中的数据包以可持续的速率传输 的机制&#xff0c;避免因为数据包太多而超过网络当前的承载能力&#xff0c;导致网络性能下降&#xff0c;甚至产生大量…...

Nginx配置文件的整体结构

一、Nginx配置文件的整体结构 从图中可以看出主要包含以下几大部分内容&#xff1a; 1. 全局块 该部分配置主要影响Nginx全局&#xff0c;通常包括下面几个部分&#xff1a; 配置运行Nginx服务器用户&#xff08;组&#xff09; worker process数 Nginx进程PID存放路径 错误…...

[SpringCloud] OpenFeign核心架构原理 (三)

文章目录 1.SpringCloud是如何整合Feign的1.1 将FeignClient接口注册到Spring中1.2 FeignClientFactoryBean相关 1.SpringCloud是如何整合Feign的 核心组件重新实现, 支持更多的SpringCloud生态的功能。将接口动态代理对象注入到Spring容器中。 1.1 将FeignClient接口注册到S…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础

第三周 Day 3 &#x1f3af; 今日目标 理解类&#xff08;class&#xff09;和对象&#xff08;object&#xff09;的关系学会定义类的属性、方法和构造函数&#xff08;init&#xff09;掌握对象的创建与使用初识封装、继承和多态的基本概念&#xff08;预告&#xff09; &a…...