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 编辑距离
题意理解: 给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字符 替换一个字符 将word1转换为word2,可以进行三种操作:增、删、改&am…...
羊大师揭秘,如何挑选出好牧场的奶羊,该怎么看
羊大师揭秘,如何挑选出好牧场的奶羊,该怎么看 了解牧场的管理和环境:好的牧场应该有规范的管理制度,环境整洁,草场茂盛,为奶羊提供了充足的食物和良好的生活环境。在这样的牧场中,奶羊能够得到…...
MySQL数据库基础(八):DML数据操作语言
文章目录 DML数据操作语言 一、DML包括哪些SQL语句 二、数据的增删改(重点) 1、数据的增加操作 2、数据的修改操作 3、数据的删除操作 DML数据操作语言 一、DML包括哪些SQL语句 insert插入、update更新、delete删除 二、数据的增删改(…...
(09)Hive——CTE 公共表达式
目录 1.语法 2. 使用场景 select语句 chaining CTEs 链式 union语句 insert into 语句 create table as 语句 前言 Common Table Expressions(CTE):公共表达式是一个临时的结果集,该结果集是从with子句中指定的查询派生而来…...
Spring 用法学习总结(四)之 JdbcTemplate 连接数据库
🐉目录 9 JdbcTemplate 9 JdbcTemplate Spring 框架对 JDBC 进行了封装,使用 JdbcTemplate 方便实现对数据库操作 相关包: 百度网盘链接https://pan.baidu.com/s/1Gw1l6VKc-p4gdqDyD626cg?pwd6666 创建properties配置文件 💥注意…...
第 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是一个开源的消息代理软件,用于在分布式系统中传递消息。它实现了高级消息队列协议(AMQP),提供了一种可靠的、强大的、灵活的消息传递机制,使得不同应用程序或组件之间可以轻松地进行通信。 二、概念…...
JWT登录验证前后端设计与实现笔记
设计内容 前端 配置全局前置路由守卫axios拦截器登录页面和主页 后端 JWT的封装登录接口中间件放行mysql数据库的连接 详细设计 路由设计 配置全局前置守卫,如果访问的是登录页面则放行,不是则进入判断是否有token,没有则拦截回到登录…...
自定义类型详解 ----结构体,位段,枚举,联合
目录 结构体 1.不完全声明 2.结构体的自引用 3.定义与初始化 4.结构体内存对齐与结构体类型的大小 结构体嵌套问题 位段 1.什么是位段? 2.位段的内存分配 枚举 1.枚举类型的定义 2.枚举的优点 联合(共同体) 1.联合体类型的声明以…...
VueCLI核心知识综合案例TodoList
目录 1 拿到一个功能模块首先需要拆分组件: 2 使用组件实现静态页面的效果 3 分析数据保存在哪个组件 4 实现添加数据 5 实现复选框勾选 6 实现数据的删除 7 实现底部组件中数据的统计 8 实现勾选全部的小复选框来实现大复选框的勾选 9 实现勾选大复选框来…...
关于cuda路径问题
问题:Could not load dynamic library ‘libcudart.so.11.0’ 原因:调用系统环境下的cuda但系统环境没有装cuda 解决: 1.在系统环境装cuda,但如果每权限就不好操作; 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(Raspberry Pi 4B)使用docker搭建springBoot/springCloud服务 前提:本文基于Ubuntu,Java8,SpringBoot 2.6.13讲解 准备工作 准备SpringBoot/SpringCloud项目jar包 用 maven 打包springBoot/springCloud项目&…...
数据库设计、JDBC、数据库连接池
数据库设计 数据库设计概念 数据库设计就是根据业务 系统的具体需求,结合我们所选用的DBMS,为这个业务系统构造出最优的数据存储模型。建立数据库中的表结构以及表与表之间的关联关系的过程。有哪些表?表里有哪些字段?表和表之间有什么关系? 数据库设计的步骤…...
SpringBoot实现OneDrive文件上传
SpringBoot实现OneDrive文件上传 源码 OneDriveUpload: SpringBoot实现OneDrive文件上传 获取accessToken步骤 参考文档:针对 OneDrive API 的 Microsoft 帐户授权 - OneDrive dev center | Microsoft Learn 1.访问Azure创建应用Microsoft Azure,使…...
C++初阶:容器适配器介绍、stack和queue常用接口详解及模拟实现
介绍完了list类的相关内容后:C初阶:适合新手的手撕list(模拟实现list) 接下来进入新的篇章,stack和queue的介绍以及模拟: 文章目录 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() 字面意思,接收单个字符,使用方法 char a; a getchar();实际上效果等同于char a; scanf("%c",&a);2.输出:putchar() 2.格式化输入输出函数 1.输入:scanf() 格式: scanf(“格式控制…...
MySQL篇之SQL优化
一、表的设计优化 表的设计优化(参考阿里开发手册《嵩山版》): 1. 比如设置合适的数值(tinyint int bigint),要根据实际情况选择。 2. 比如设置合适的字符串类型(char和varchar)…...
QGis —— 1、Windows10下载安装QGis及插件
QGis官网 QGIS(自由开源的地理信息系统)是一个专业的GIS应用程序,它建立在免费和开源软件(FOSS)之上,并为此而自豪。QGIS 是一个方便使用的开源地理信息系统 (GIS),根据 GNU 通用公共许可授权。…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...
springboot 日志类切面,接口成功记录日志,失败不记录
springboot 日志类切面,接口成功记录日志,失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...
