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

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

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

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

Axios请求超时重发机制

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

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...