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

Leetcode 72 编辑距离

题意理解:

        给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数  。

        你可以对一个单词进行如下三种操作:

                插入一个字符

                删除一个字符

                替换一个字符

        将word1转换为word2,可以进行三种操作:增、删、改,最少操作几次

        其中特别注意:增和删为互逆操作,其效果是一样的:在word1删除一个元素或在word2添加一个元素,都是进行一次操作效果。

        这里我们使用动态规划来进行解题。

解题思路:

        (1)定义dp数组

                dp[i][j]表示word1第i个元素前,word2第j个元素前,使word1转换为word2最少需要操作的次数。

        (2)递推公式:

           当word1[i-1]==word2[j-1]时

            无需操作: dp[i][j]=dp[i-1][j-1]

          否则:

                增|删:dp[i-1][j]+1   或   dp[i][j-1]+1

                改:    dp[i-1][j-1]+1

                即: dp[i][j]=Math.min(Math.min(dp[i-1][j]+1 ,dp[i][j-1]+1),  dp[i-1][j-1]+1 )

          (3) 初始化:

                dp[i][0] 表示把word1变为空串,则产出i个元素,即dp[i][0]=i

                同理: dp[0][j]=j                       

1.动态规划解题

public int minDistance(String word1, String word2) {int [][] dp=new int[word1.length()+1][word2.length()+1];for(int i=0;i<=word1.length();i++){dp[i][0]=i;}for(int j=1;j<=word2.length();j++){dp[0][j]=j;}for(int i=1;i<=word1.length();i++){for(int j=1;j<=word2.length();j++){if(word1.charAt(i-1)==word2.charAt(j-1)){//不操作dp[i][j]=dp[i-1][j-1];}else {dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1])+1,dp[i-1][j-1]+1);}}}return dp[word1.length()][word2.length()];}

2.复杂度分析 

时间复杂度:O(n^2)

空间复杂度:O(n^2)

相关文章:

Leetcode 72 编辑距离

题意理解&#xff1a; 给你两个单词 word1 和 word2&#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作&#xff1a; 插入一个字符 删除一个字符 替换一个字符 将word1转换为word2,可以进行三种操作&#xff1a;增、删、改&am…...

羊大师揭秘,如何挑选出好牧场的奶羊,该怎么看

羊大师揭秘&#xff0c;如何挑选出好牧场的奶羊&#xff0c;该怎么看 了解牧场的管理和环境&#xff1a;好的牧场应该有规范的管理制度&#xff0c;环境整洁&#xff0c;草场茂盛&#xff0c;为奶羊提供了充足的食物和良好的生活环境。在这样的牧场中&#xff0c;奶羊能够得到…...

MySQL数据库基础(八):DML数据操作语言

文章目录 DML数据操作语言 一、DML包括哪些SQL语句 二、数据的增删改&#xff08;重点&#xff09; 1、数据的增加操作 2、数据的修改操作 3、数据的删除操作 DML数据操作语言 一、DML包括哪些SQL语句 insert插入、update更新、delete删除 二、数据的增删改&#xff08…...

(09)Hive——CTE 公共表达式

目录 1.语法 2. 使用场景 select语句 chaining CTEs 链式 union语句 insert into 语句 create table as 语句 前言 Common Table Expressions&#xff08;CTE&#xff09;&#xff1a;公共表达式是一个临时的结果集&#xff0c;该结果集是从with子句中指定的查询派生而来…...

Spring 用法学习总结(四)之 JdbcTemplate 连接数据库

&#x1f409;目录 9 JdbcTemplate 9 JdbcTemplate Spring 框架对 JDBC 进行了封装&#xff0c;使用 JdbcTemplate 方便实现对数据库操作 相关包&#xff1a; 百度网盘链接https://pan.baidu.com/s/1Gw1l6VKc-p4gdqDyD626cg?pwd6666 创建properties配置文件 &#x1f4a5;注意…...

第 385 场 LeetCode 周赛题解

A 统计前后缀下标对 I 模拟 class Solution { public:int countPrefixSuffixPairs(vector<string> &words) {int n words.size();int res 0;for (int i 0; i < n; i)for (int j i 1; j < n; j)if (words[i].size() < words[j].size()) {int li words[…...

什么是RabbitMQ?

一、引言 RabbitMQ是一个开源的消息代理软件&#xff0c;用于在分布式系统中传递消息。它实现了高级消息队列协议&#xff08;AMQP&#xff09;&#xff0c;提供了一种可靠的、强大的、灵活的消息传递机制&#xff0c;使得不同应用程序或组件之间可以轻松地进行通信。 二、概念…...

JWT登录验证前后端设计与实现笔记

设计内容 前端 配置全局前置路由守卫axios拦截器登录页面和主页 后端 JWT的封装登录接口中间件放行mysql数据库的连接 详细设计 路由设计 配置全局前置守卫&#xff0c;如果访问的是登录页面则放行&#xff0c;不是则进入判断是否有token&#xff0c;没有则拦截回到登录…...

自定义类型详解 ----结构体,位段,枚举,联合

目录 结构体 1.不完全声明 2.结构体的自引用 3.定义与初始化 4.结构体内存对齐与结构体类型的大小 结构体嵌套问题 位段 1.什么是位段&#xff1f; 2.位段的内存分配 枚举 1.枚举类型的定义 2.枚举的优点 联合&#xff08;共同体&#xff09; 1.联合体类型的声明以…...

VueCLI核心知识综合案例TodoList

目录 1 拿到一个功能模块首先需要拆分组件&#xff1a; 2 使用组件实现静态页面的效果 3 分析数据保存在哪个组件 4 实现添加数据 5 实现复选框勾选 6 实现数据的删除 7 实现底部组件中数据的统计 8 实现勾选全部的小复选框来实现大复选框的勾选 9 实现勾选大复选框来…...

关于cuda路径问题

问题&#xff1a;Could not load dynamic library ‘libcudart.so.11.0’ 原因&#xff1a;调用系统环境下的cuda但系统环境没有装cuda 解决&#xff1a; 1.在系统环境装cuda&#xff0c;但如果每权限就不好操作&#xff1b; 2.用虚拟环境装好的cuda路径丢给环境变量 暂时性&am…...

六、Spring/Spring Boot整合ActiveMQ

Spring/Spring Boot整合ActiveMQ 一、Spring整合ActiveMQ1.pom.xml2.Queue - 队列2.1 applicationContext.xml2.2 生产者2.3 消费者 3.Topic - 主题3.1 applicationContext.xml3.2 生产者3.3 消费者 4.消费者 - 监听器4.1 编写监听器类4.2 配置监听器4.3 生产者消费者一体 二、…...

树莓派4B(Raspberry Pi 4B)使用docker搭建springBoot/springCloud服务

树莓派4B&#xff08;Raspberry Pi 4B&#xff09;使用docker搭建springBoot/springCloud服务 前提&#xff1a;本文基于Ubuntu&#xff0c;Java8&#xff0c;SpringBoot 2.6.13讲解 准备工作 准备SpringBoot/SpringCloud项目jar包 用 maven 打包springBoot/springCloud项目&…...

数据库设计、JDBC、数据库连接池

数据库设计 数据库设计概念 数据库设计就是根据业务 系统的具体需求&#xff0c;结合我们所选用的DBMS,为这个业务系统构造出最优的数据存储模型。建立数据库中的表结构以及表与表之间的关联关系的过程。有哪些表?表里有哪些字段?表和表之间有什么关系? 数据库设计的步骤…...

SpringBoot实现OneDrive文件上传

SpringBoot实现OneDrive文件上传 源码 OneDriveUpload: SpringBoot实现OneDrive文件上传 获取accessToken步骤 参考文档&#xff1a;针对 OneDrive API 的 Microsoft 帐户授权 - OneDrive dev center | Microsoft Learn 1.访问Azure创建应用Microsoft Azure&#xff0c;使…...

C++初阶:容器适配器介绍、stack和queue常用接口详解及模拟实现

介绍完了list类的相关内容后&#xff1a;C初阶&#xff1a;适合新手的手撕list&#xff08;模拟实现list&#xff09; 接下来进入新的篇章&#xff0c;stack和queue的介绍以及模拟&#xff1a; 文章目录 1.stack的初步介绍2.stack的使用3.queue的初步介绍4.queue的使用5.容器适…...

GRUB and the Boot Process on UEFI-based x86 Systems

background info : BIOS and UEFI-CSDN博客 The UEFI-based platform reads the partition table on the system storage and mounts the EFI System Partition (ESP), a VFAT partition labeled with a particular globally unique identifier (GUID). The ESP contains EFI a…...

2.C语言——输入输出

1.字符输入输出函数 1.输入:getchar() 字面意思&#xff0c;接收单个字符&#xff0c;使用方法 char a; a getchar();实际上效果等同于char a; scanf("%c",&a);2.输出:putchar() 2.格式化输入输出函数 1.输入:scanf() 格式&#xff1a; scanf(“格式控制…...

MySQL篇之SQL优化

一、表的设计优化 表的设计优化&#xff08;参考阿里开发手册《嵩山版》&#xff09;&#xff1a; 1. 比如设置合适的数值&#xff08;tinyint int bigint&#xff09;&#xff0c;要根据实际情况选择。 2. 比如设置合适的字符串类型&#xff08;char和varchar&#xff09…...

QGis —— 1、Windows10下载安装QGis及插件

QGis官网 QGIS&#xff08;自由开源的地理信息系统&#xff09;是一个专业的GIS应用程序&#xff0c;它建立在免费和开源软件&#xff08;FOSS&#xff09;之上&#xff0c;并为此而自豪。QGIS 是一个方便使用的开源地理信息系统 (GIS)&#xff0c;根据 GNU 通用公共许可授权。…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

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

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

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...