leetcode hot100【Leetcode 72.编辑距离】java实现
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 -> exention (替换 'i' 为 'e')
exention -> exection (替换 'n' 为 'c')
exection -> execuion (替换 'e' 为 'u')
execuion -> execution (替换 'i' 为 't')
Java 实现代码
public class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();// dp[i][j] 表示 word1[0..i-1] 和 word2[0..j-1] 的最小编辑距离int[][] dp = new int[m + 1][n + 1];// 初始化 DP 数组for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0) {dp[i][j] = j; // 如果 word1 为空,需要插入 j 个字符} else if (j == 0) {dp[i][j] = i; // 如果 word2 为空,需要删除 i 个字符} else {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]), dp[i - 1][j - 1]) + 1;// 三种操作的最小值:删除、插入、替换}}}}return dp[m][n];}
}
解题思路
编辑距离问题是一个经典的动态规划问题,我们可以通过动态规划来逐步解决。
状态定义:
- 定义
dp[i][j]为word1[0..i-1]和word2[0..j-1]之间的最小编辑距离。状态转移:
- 如果
word1[i-1] == word2[j-1],则dp[i][j] = dp[i-1][j-1],表示如果两个字符相等,编辑距离不变。- 如果
word1[i-1] != word2[j-1],则dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1,表示三种操作的最小值:
dp[i-1][j] + 1:删除一个字符。dp[i][j-1] + 1:插入一个字符。dp[i-1][j-1] + 1:替换一个字符。初始状态:
dp[i][0] = i,表示word1[0..i-1]和空字符串的编辑距离是i(即删除所有字符)。dp[0][j] = j,表示 空字符串 和word2[0..j-1]的编辑距离是j(即插入所有字符)。目标:
- 最终结果为
dp[m][n],其中m和n分别是word1和word2的长度。
复杂度分析
时间复杂度:
O(m * n),其中m和n分别是word1和word2的长度。我们需要计算一个m x n的 DP 表格,每个元素的计算是常数时间。空间复杂度:
O(m * n),我们需要一个m x n的 DP 表格来存储子问题的解。
执行过程示例
假设 word1 = "horse",word2 = "ros",我们通过动态规划计算编辑距离。
-
初始化 DP 数组:
dp = [[0, 1, 2, 3],[1, 0, 0, 0],[2, 0, 0, 0],[3, 0, 0, 0],[4, 0, 0, 0],[5, 0, 0, 0] ] -
填充 DP 数组:
i = 1, j = 1,word1[0] = 'h',word2[0] = 'r',不相等,dp[1][1] = min(dp[0][1], dp[1][0], dp[0][0]) + 1 = 1。i = 1, j = 2,word1[0] = 'h',word2[1] = 'o',不相等,dp[1][2] = min(dp[0][2], dp[1][1], dp[0][1]) + 1 = 2。i = 1, j = 3,word1[0] = 'h',word2[2] = 's',不相等,dp[1][3] = min(dp[0][3], dp[1][2], dp[0][2]) + 1 = 3。i = 2, j = 1,word1[1] = 'o',word2[0] = 'r',不相等,dp[2][1] = min(dp[1][1], dp[2][0], dp[1][0]) + 1 = 2。i = 2, j = 2,word1[1] = 'o',word2[1] = 'o',相等,dp[2][2] = dp[1][1] = 1。i = 2, j = 3,word1[1] = 'o',word2[2] = 's',不相等,dp[2][3] = min(dp[1][3], dp[2][2], dp[1][2]) + 1 = 2。i = 3, j = 1,word1[2] = 'r',word2[0] = 'r',相等,dp[3][1] = dp[2][0] = 2。i = 3, j = 2,word1[2] = 'r',word2[1] = 'o',不相等,dp[3][2] = min(dp[2][2], dp[3][1], dp[2][1]) + 1 = 2。i = 3, j = 3,word1[2] = 'r',word2[2] = 's',不相等,dp[3][3] = min(dp[2][3], dp[3][2], dp[2][2]) + 1 = 3。i = 4, j = 1,word1[3] = 's',word2[0] = 'r',不相等,dp[4][1] = min(dp[3][1], dp[4][0], dp[3][0]) + 1 = 3。i = 4, j = 2,word1[3] = 's',word2[1] = 'o',不相等,dp[4][2] = min(dp[3][2], dp[4][1], dp[3][1]) + 1 = 3。- `i = 4, j = 3
,word1[3] = ‘s’, word2[2] = ‘s’,相等,dp[4][3] = dp[3][2] = 2`。
i = 5, j = 1,word1[4] = 'e',word2[0] = 'r',不相等,dp[5][1] = min(dp[4][1], dp[5][0], dp[4][0]) + 1 = 4。i = 5, j = 2,word1[4] = 'e',word2[1] = 'o',不相等,dp[5][2] = min(dp[4][2], dp[5][1], dp[4][1]) + 1 = 4。i = 5, j = 3,word1[4] = 'e',word2[2] = 's',不相等,dp[5][3] = min(dp[4][3], dp[5][2], dp[4][2]) + 1 = 3。
-
最终 DP 数组:
dp = [[0, 1, 2, 3],[1, 1, 2, 3],[2, 2, 1, 2],[3, 2, 2, 3],[4, 3, 3, 2],[5, 4, 4, 3] ] -
结果为
dp[5][3] = 3,即编辑距离为 3。
相关文章:
leetcode hot100【Leetcode 72.编辑距离】java实现
Leetcode 72.编辑距离 题目描述 给定两个单词 word1 和 word2,返回将 word1 转换为 word2 所使用的最少操作数。 你可以对一个单词执行以下三种操作之一: 插入一个字符删除一个字符替换一个字符 示例 1: 输入: word1 "horse", word2 &…...
腾讯阅文集团Java后端开发面试题及参考答案
Java 的基本数据类型有哪些?Byte 的数值范围是多少? Java 的基本数据类型共有 8 种,可分为 4 类: 整数类型:包括 byte、short、int 和 long。byte 占 1 个字节,其数值范围是 - 128 到 127,用于表示较小范围的整数,节省内存空间,在处理一些底层的字节流数据或对内存要求…...
protobuf实现Hbase数据压缩
目录 前置HBase数据压缩效果获取数据(反序列化) 前置 安装说明 使用说明 HBaseDDL和DML操作 HBase数据压缩 问题 在上文的datain中原文 每次写入数据会写入4个单元格的内容,现在希望能对其进行筛减,合并成1格,减少存储空间(序列…...
论文阅读之方法: Single-cell transcriptomics of 20 mouse organs creates a Tabula Muris
The Tabula Muris Consortium., Overall coordination., Logistical coordination. et al. Single-cell transcriptomics of 20 mouse organs creates a Tabula Muris. Nature 562, 367–372 (2018). 论文地址:https://doi.org/10.1038/s41586-018-0590-4 代码地址…...
PHP语法学习(第三天)
老规矩,先回顾一下昨天学习的内容 PHP语法学习(第二天) 主要学习了PHP变量、变量的作用域、以及参数作用域。 今天由Tom来打开新的篇章 文章目录 echo 和 print 区别PHP echo 语句实例 PHP print 语句实例 PHP 数组创建数组利用array() 函数 数组的类型索引数组关联…...
PostgreSQL添加PostGIS扩展和存储坐标
一、安装 1、PostGIS安装:Getting Started | PostGIS 2、安装好后,执行下面sql CREATE EXTENSION postgis;SELECT PostGIS_Full_Version(); 二、使用 PostGIS文档:PostGIS 简介 — Introduction to PostGIS 建表: CREATE TAB…...
Flink四大基石之State(状态) 的使用详解
目录 一、有状态计算与无状态计算 (一)概念差异 (二)应用场景 二、有状态计算中的状态分类 (一)托管状态(Managed State)与原生状态(Raw State) 两者的…...
Linux中dos2unix详解
dos2unix 是一个用于将文本文件从DOS/Windows格式转换为Unix/Linux格式的工具。在不同的操作系统中,文本文件中的换行符表示方式是不一样的。具体来说: 在DOS和Windows系统中,换行由两个字符组成:回车(Carriage Retur…...
MySQL MVCC 介绍
MVCC(Multi-Version Concurrency Control)是一种并发控制机制,用于在多个并发事务同时读写数据库时保持数据的一致性和隔离性。MVCC通过在每个数据行上维护多个版本的数据来实现。当一个事务要对数据库中的数据进行修改时,MVCC不会…...
Linux篇之日志管理工具Logrotate介绍并结合crontab使用
1. Logrotate介绍 logrotate 是一个用于管理和轮换日志文件的工具,通常用于 Unix 和 Linux 系统。它可以自动化日志文件的轮换、压缩、删除和邮寄等操作,确保日志文件不会无限制地增长,占用过多的磁盘空间。 2. 主要功能 轮换:定期将日志文件移动到备份目录,并生成新的…...
Vulnhub靶场 Matrix-Breakout: 2 Morpheus 练习
目录 0x00 准备0x01 主机信息收集0x02 站点信息收集0x03 漏洞查找与利用1. 文件上传2. 提权 0x04 总结 0x00 准备 下载连接:https://download.vulnhub.com/matrix-breakout/matrix-breakout-2-morpheus.ova 介绍: This is the second in the Matrix-Br…...
秒杀项目 超卖问题 详解
秒杀项目中的超卖问题详解 秒杀场景是一种高并发场景,用户在短时间内大量涌入抢购有限的商品。超卖问题指的是由于系统设计不合理,导致实际售出的商品数量超过库存数量。 1. 为什么会出现超卖问题? 超卖问题通常由以下原因引发:…...
Linux系统编程之进程控制
概述 在Linux系统中,创建一个新的进程后,如何对该进程进行有效的控制,是一项非常重要的操作。控制进程状态的操作主要包括:进程的执行、进程的等待、进程的终止等。下面,我们将逐个进行介绍。 进程的执行 创建进程后&a…...
集合的相关性质与定义
集合 集合 集合描述了一组对象的集合,而映射描述了集合之间的对应关系。 集合 集合是由一组无序的,互不相同的对象组成的整体,集合中的对象称为元素或成员。集合可以用大括号{}表示,元素之间用逗号进行分隔。 定义: 集合 A …...
pytest自定义命令行参数
实际使用场景:pytest运行用例的时候,启动mitmdump进程试试抓包,pytest命令行启动的时候,传入mitmdump需要的参数(1)抓包生成的文件地址 (2)mitm的proxy设置 # 在pytest的固定文件中…...
c++预编译头文件
文章目录 c预编译头文件1.使用g编译预编译头文件2.使用visual studio进行预编译头文件2.1visual studio如何设置输出预处理文件(.i文件)2.2visual studio 如何设置预编译(初始创建空项目的情况下)2.3 visual studio打开输出编译时…...
YOLOv8模型pytorch格式转为onnx格式
一、YOLOv8的Pytorch网络结构 model DetectionModel((model): Sequential((0): Conv((conv): Conv2d(3, 64, kernel_size(3, 3), stride(2, 2), padding(1, 1))(act): SiLU(inplaceTrue))(1): Conv((conv): Conv2d(64, 128, kernel_size(3, 3), stride(2, 2), padding(1, 1))(a…...
电子课程开发中的典型误区
创建一个有效的电子课程需要仔细的规划和执行,但常见的错误可能会破坏其成功。以下是开发人员应该避免的一些典型陷阱: 1.缺乏明确的目标 如果没有明确的学习目标,课程可能会缺乏重点,让学习者不确定自己应该实现什么。明确、可衡…...
Docker 逃逸突破边界
免责声明 本博客文章仅供教育和研究目的使用。本文中提到的所有信息和技术均基于公开来源和合法获取的知识。本文不鼓励或支持任何非法活动,包括但不限于未经授权访问计算机系统、网络或数据。 作者对于读者使用本文中的信息所导致的任何直接或间接后果不承担任何…...
残差连接,就是当某一偏导等于0时,加上x偏导就是1,这样乘以1保证不失效
目录 残差连接,就是当某一偏导等于0时,加上x偏导就是1,这样乘以1保证不失效 残差连接中F(x)一般代表什么,将F(x)变为F(x) +x,这样不是改变了函数 本身的性质 F(x)=F(x) +x F(x)偏导若==0;偏导连乘就是0,这样就梯度消失了 F(x) +x;求偏导时x导数是1,保证不丢失F(x)…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
学习一下用鸿蒙DevEco Studio HarmonyOS5实现百度地图
在鸿蒙(HarmonyOS5)中集成百度地图,可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API,可以构建跨设备的定位、导航和地图展示功能。 1. 鸿蒙环境准备 开发工具:下载安装 De…...
