【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 <= 500word1和word2由小写英文字母组成
解答
源代码
class Solution {public int minDistance(String word1, String word2) {int m = word1.length(), n = word2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 0; i < m + 1; i++) {dp[i][0] = i;}for (int i = 0; i < n + 1; i++) {dp[0][i] = i;}for (int i = 1; i < m + 1; i++) {for (int j = 1; j < n + 1; 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][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;}}}return dp[m][n];}
}
总结
动态规划:
dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
所以,
当 word1[i] == word2[j],dp[i][j] = dp[i-1][j-1];
当 word1[i] != word2[j],dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
其中,dp[i-1][j-1] 表示替换操作,dp[i-1][j] 表示删除操作,dp[i][j-1] 表示插入操作。
注意,针对第一行,第一列要单独考虑,我们引入' ',word.charAt(0) = ' '。
相关文章:
【LeetCode】72.编辑距离
题目 给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符删除一个字符替换一个字符 示例 1: 输入:word1 "horse", word2 "…...
大模型,开源干不掉闭源
开源大模型对闭源大模型的冲击,变得非常猛烈。 今年3月,Meta发布了Llama(羊驼),很快成为AI社区内最强大的开源大模型,也是许多模型的基座模型。有人戏称,当前的大模型集群,就是一堆各…...
Redis 九种数据类型的基本操作
一、redis9种数据类型的基本操作 ①key操作 #查找所有的key 127.0.0.1:6379> keys * 1) "pop" 2) "mylist" 3) "lpl" 4) "myset" #设置key的过期时间 返回1表示执行成功,0表示失败,出现问题 127.0.0.1:6379…...
爬取微博热搜榜并进行数据分析
设计方案 爬虫爬取的内容 :爬取微博热搜榜数据。 网络爬虫设计方案概述 用requests库访问页面用get方法获取页面资源,登录页面对页面HTML进行分析,用beautifulsoup库获取并提取自己所需要的信息。再讲数据保存到CSV文件中,进行…...
基于深度神经网络的肺炎检测系统实现
一、说在前面 使用AI进行新冠肺炎图像诊断可以加快病例的诊断速度,提高诊断的准确性,并在大规模筛查中发挥重要作用,从而更好地控制和管理这一流行病。然而,需要强调的是,AI技术仅作为辅助手段,最终的诊断决…...
C# LINQ和Lambda表达式对照
C# LINQ和Lambda表达式对照 1. 基本查询语句 Linq语法: var datafrom a in db.Areas select a ; Lamda语法: var datadb.Areas; sql语法: SELECT * FROM Areas2. 简单的WHERE语句 Linq语法: var datafrom a in db.orderI…...
二、SQL-6.DCL-1).用户管理
一、DCL介绍 Data Control Language 数据控制语言 用来管理数据库 用户、控制数据库的 访问权限。 二、语法 1、管理用户 管理用户在系统数据库mysql中的user表中创建、删除一个用户,需要Host(主机名)和User(用户名࿰…...
ElasticSearch学习--数据聚合
介绍 数据聚合可以帮助我们对海量的数据进行统计分析,如果结合kibana,我们还能形成可视化的图形报表。自动补全可以根据用户输入的部分关键字去自动补全和提示。数据同步可以帮助我们解决es和mysql的数据一致性问题。集群可以帮助我们了解结构和不同节点…...
PostMan+Jmeter工具介绍及安装
目录 一、PostMan介绍编辑 二、下载安装 三、Postman与Jmeter的区别 一、开发语言区别: 二、使用范围区别: 三、使用区别: 四、Jmeter安装 附一个详细的Jmeter按照新手使用教程,感谢作者,亲测有效。 五、Jme…...
AutoSAR系列讲解(实践篇)7.4-实验:配置SWCRTE
注意: 实验篇是重点,有条件的同学最好跟着做一遍,然后回头对照着7.1-7.3理解其配置的目的和意义。实验下篇将在7.7节中继续做 一、实验概览 1、实验目的 通过本次实验,主要是让大家对Dev的配置有一个全流程的学习。这里会用到前两节的内容,将其串联起来,让大家能完整的…...
腾讯云内存型CVM服务器MA3、M6、M6ce和M5处理器CPU说明
腾讯云内存型CVM服务器CPU处理器大全,CVM内存型MA3、内存型M6、安全增强内存型M6ce、内存型M6p、内存型M5、MA2、M4、M3、M2、M1处理器主频、CPU性能性能大全说明,腾讯云内存型云服务器具有大内存的特点,适合高性能数据库、分布式内存缓存等需…...
集睿致远推出CS5466多功能拓展坞方案:支持DP1.4、HDMI2.1视频8K输出
ASL新推出的 CS5466是一款Type-C/DP1.4转HDMI2.1的显示协议转换芯片,,它通过类型C/显示端口链路接收视频和音 频流,并转换为支持TMDS或FRL输出信令。DP接收器支持81.Gbp s链路速率。HDMI输出端口可以作为TMDS或FRL发射机工作。FRL发射机符合HDMI 2.1规范…...
SQL中为何时常见到 where 1=1?
你是否曾在 SELECT 查询中看到过 WHERE 11 条件。我在许多不同的查询和许多 SQL 引擎中都有看过。这条件显然意味着 WHERE TRUE,所以它只是返回与没有 WHERE 子句时相同的查询结果。此外,由于查询优化器几乎肯定会删除它,因此对查询执行时间没…...
React AntDesign表批量操作时的selectedRowKeys回显选中
不知道大家是不是在AntDesign的某一个列表想要做一个批量导出或者操作的时候,发现只要选择下一页,即使选中的ids 都有记录下面,但是就是不回显 后来问了chatGPT,对方的回答是: 在Ant Design的DataTable组件中…...
anydesk远程控制,主动连接。
目标 远程控制目标电脑,且无需对方同意,并且可以控制目标电脑开关机。 实现 目标电脑和己方电脑均安装anydesk。目标电脑取消开机密码。打开目标电脑的anydesk在设置安全设置中打开为自主访问设置密码。 额外设置 为了让笔记本电脑合盖后仍能被控制…...
Spring Data Redis操作Redis
在Spring Boot项目中,可以使用Spring Data Redis来简化Redis操作,maven的依赖坐标: <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></…...
sqlite触发器1
SQLite 的触发器(Trigger)可以指定在特定的数据库表发生 DELETE、INSERT 或 UPDATE 时触发,或在一个或多个指定表的列发生更新时触发。 SQLite 只支持 FOR EACH ROW 触发器(Trigger),没有 FOR EACH STATEM…...
python中——requests爬虫【中文乱码】的3种解决方法
requests是一个较为简单易用的HTTP请求库,是python中编写爬虫程序最基础常用的一个库。 而【中文乱码】问题,是最常遇到的问题,对于初学者来说,是很困恼的。 本文将详细说明,python中使用requests库编写爬虫程序时&…...
E. Nastya and Potions(DFS+记忆化搜索)
炼金术士纳斯蒂亚喜欢混合药剂。一共有n种药剂,ci硬币可以买到一种 i 型药剂。 任何一种药剂都只能通过一种方式获得,即混合其他几种药剂。混合过程中使用的药剂将被消耗掉。此外,任何药剂都不能通过一个或多个混合过程从自身获得。 作为一名…...
什么是tcp rst以及什么时候产生?
rst包是仅在header control bits设置rst的空payload包,用于强制关闭tcp连接。常在以下场景发送 远程主机没有监听该端口 远程主机强迫关闭了一个现有连接。比如服务端进程崩溃后重启会向之前连接发送rst 相比于四次挥手的fin,rst是在异常情况下的无条…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
