代码随想录打卡第五十八天|● 583. 两个字符串的删除操作 ● 72. 编辑距离
583. 两个字符串的删除操作
题目: 给定两个单词 word1 和 word2 ,返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。

题目链接: 583. 两个字符串的删除操作
解题思路:
dp数组的含义:w1[:i-1]与w2[:j-1]相同的最小删除次数
比较当前字母
如果两个字母相同,则不用进行删除操作
即dp[i][j]=dp[i-1][j-1]
如果两个字母不同,要么删除w1 要么删除w2 要么两者都删 取三者最小值
即dp[i][j]=max(dp[i-1][j]+1(删1),dp[i][j-1]+1(删2),dp[i-1][j-1]+2(都删)) 后面的+1和+2是删除的操作次数
代码如下:
class Solution {public int minDistance(String word1, String word2) {//相同 不删 dp[i][j]=dp[i-1][j-1];//不同 删1 删2 都删 dp[i][j]=max(dp[i-1][j]+1(删1),dp[i][j-1]+1(删2),dp[i-1][j-1]+2(都删))int[][] dp=new int[word1.length()+1][word2.length()+1];//初始化int temp=0;for(int i=0;i<=word1.length();i++){dp[i][0]=temp;temp++;}temp=0;for(int j=0;j<=word2.length();j++){dp[0][j]=temp;temp++;}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]+1,dp[i][j-1]+1),dp[i-1][j-1]+2);}}}return dp[word1.length()][word2.length()];}
}
72. 编辑距离(重点复习)
题目: 给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符

题目链接: 72. 编辑距离
解题思路:
相同时 不变 即 dp[i][j]=dp[i-1][j-1];
不同时 取三种操作的最小值 dp[i][j]=Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
删除w1和添加w2是逆操作 删除w2与添加w1是逆操作 所以写删除或添加即可 这里写删除操作
改操作 dp[i-1][j-1]+1 将 i,j改成相同的值
代码如下
class Solution {public int minDistance(String word1, String word2) {//相同时 不变//不同时 取三种操作的最小值//删除w1和添加w2是逆操作 删除w2与添加w1是逆操作 所以写删除或添加即可 这里写删除操作//改 dp[i-1][j-1]+1 将 i,j改成相同的值int[][] dp=new int[word1.length()+1][word2.length()+1];//初始化int temp=0;for(int i=0;i<=word1.length();i++){dp[i][0]=temp;temp++;}temp=0;for(int j=0;j<=word2.length();j++){dp[0][j]=temp;temp++;}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]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);}}}return dp[word1.length()][word2.length()];}
}
相关文章:
代码随想录打卡第五十八天|● 583. 两个字符串的删除操作 ● 72. 编辑距离
583. 两个字符串的删除操作 题目: 给定两个单词 word1 和 word2 ,返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 题目链接: 583. 两个字符串的删除操作 解题思路: dp数组的含义&am…...
面试流程之——程序员如何写项目经验
在简历中介绍IT项目经验,你可以遵循以下步骤: 明确项目目标:首先,清晰地阐述项目的目标。这可以是提升某个软件的性能,改进某个系统的用户界面,或者增加某款产品的功能。让读者了解你的工作与项目的整体目…...
框架安全-CVE 漏洞复现DjangoFlaskNode.jsJQuery框架漏洞复现
目录 服务攻防-框架安全&CVE复现&Django&Flask&Node.JS&JQuery漏洞复现中间件列表介绍常见语言开发框架Python开发框架安全-Django&Flask漏洞复现Django开发框架漏洞复现CVE-2019-14234(Django JSONField/HStoreField SQL注入漏洞ÿ…...
基于SSM的理发店管理系统
基于SSM的理发店管理系统的设计与实现~ 开发语言:Java数据库:MySQL技术:SpringSpringMVCMyBatis工具:IDEA/Ecilpse、Navicat、Maven 系统展示 主页 公告信息 管理员界面 用户界面 摘要 基于SSM(Spring、Spring MVC、…...
2.Spark的工作与架构原理
概述 目标: spark的工作原理spark数据处理通用流程rdd 什么是rddrdd 的特点 spark架构 spark架构相关进程spark架构原理 spark的工作原理 spark 的工作原理,如下图 图中中间部分是spark集群,也可以是基于 yarn 的,图上可以…...
qt-C++笔记之带有倒计数显示的按钮,计时期间按钮锁定
qt-C笔记之带有倒计数显示的按钮,计时期间按钮锁定 code review! 文章目录 qt-C笔记之带有倒计数显示的按钮,计时期间按钮锁定1.运行2.main.cc3.main.pro 1.运行 2.main.cc 代码 #include <QApplication> #include <QPushButton> #includ…...
HTML全局属性(global attribute)有哪些?
HTML全局属性是指在HTML元素上可用的基本属性,它们适用于所有HTML元素。以下是一些常见的HTML全局属性: 1:class:为元素指定一个或多个类名,用于与CSS样式表关联。 2:id::为元素指定唯一的标识…...
MyBatis-Plus返回getOne返回null疑惑
getOne返回null 问题描述分析过程总结 问题描述 在数据库建了一张表主要包括两个字段master_id和slave_id;主要的额外字段max_lots 默认值是null; 当调用getOne进行查询结果是null,但实际情况是数据库时应该返回值的; AotfxMasterSlave ex…...
Physics2DPlugin3加载后会跳转gsap官网解决
因工作需要使用Physics2DPlugin3库,目标效果 加载他里面的在线js,使用效果正常,但是几秒会跳转官网,我们app内部、浏览器都会这样。 于是研究js代码,发现里面有setTimeout跳转。 删掉就好了 分享我改好的文件&#x…...
【AI视野·今日Sound 声学论文速览 第三十二期】Tue, 24 Oct 2023
AI视野今日CS.Sound 声学论文速览 Tue, 24 Oct 2023 Totally 20 papers 👉上期速览✈更多精彩请移步主页 Interesting: 📚nvas3d, 基于任意录音和室内3D信息合成重建不同听角(位置)处的新的声音。(from apple cmu) website: htt…...
在Linux上编译gdal3.1.2指南
作者:朱金灿 来源:clever101的专栏 为什么大多数人学不会人工智能编程?>>> 以Ubuntu 18编译gdal3.1.2为例,编译gdal3.1.2需要先编译proj库和geos库(可选)。我选择的proj库版本为proj-7.1.0,编译proj-7.1.0需要先编译tiff库和sqlite3。我选择的sqlite3的版本为…...
73. 矩阵置零 --力扣 --JAVA
题目 给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 解题思路 通过二层循环找出元素为0所在的行和列;设置标志位记录当前行是否存在元素为0的,设置列表存储列为0的列&#…...
(笔记)Kotlin——Android封装ViewBinding之二 优化
0. 在app模块的build.gradle文件中添加如下配置开启ViewBinding android {.......viewBinding {enabled true}} 1. 新建一个Ext.kt文件 添加两个扩展函数,分别对应Activity和Fragment inline fun <T : ViewBinding> AppCompatActivity.viewBinding(cross…...
MATLAB算法实战应用案例精讲-【图像处理】机器视觉(基础篇)(八)
目录 前言 几个高频面试题目 机器视觉如何获取到好图像 常见的视觉光源 各种视觉打光方式...
由k8s升级慢引起的etcd性能不足的问题排查
一、基本介绍 最近etcd查看出现性能 curl --cacert /path/to/etcdctl-ca.crt --cert /path/to/etcdctl.crt --key /path/to/etcdctl.key https://:2379/metrics | grep etcd_disk_wal_fsync_duration_seconds_bucket 当集群规模突破过大时规模时,曾出现如下性能瓶颈问题: etc…...
如何构建用于Skydel GNSS模拟仿真的SNMP代理方式?
使用Skydel API构建测试方案 凭借其现代、强大且直观的API,德思特Safran GNSS模拟引擎Skydel免费提供了Python、C#、C和Labview的开源客户端库,它具有600多条命令,并且有完善的文档与记录。 随着Skydel软件更新添加新功能,API得…...
vue2+ant-design-vue a-form-model组件二次封装(form表单组件)FormModel 表单
一、效果图 二、参数配置 1、代码示例 <t-antd-form:ref-obj.sync"formOpts.ref":formOpts"formOpts":widthSize"1":labelCol"{ span:2}":wrapperCol"{ span:22}"handleEvent"handleEvent" />2. 配置参数…...
对比解析php和go对JSON处理的区别
一、go 转化php数组代码 php程序 $str <<<EOF {"操作源":"任意","数据库":"任意","语句类型":"CREATE DATABASE;DROP DATABASE;ALTER DATABASE","影响行数":"不…...
HTTP和HTTPS本质区别——SSL证书
HTTP和HTTPS是两种广泛使用的协议,尽管它们看起来很相似,但是它们在网站数据传输的安全性上有着本质上的区别。 HTTP是明文传输协议,意味着通过HTTP发送的数据是未经加密的,容易受到拦截、窃听和篡改的风险。而HTTPS通过使用SSL或…...
JS 防抖和节流
防抖(debounce)和节流(throttle)是JavaScript中常用的性能优化技术,用于限制某些高频率触发的函数执行次数,减少不必要的计算和网络请求。下面分别介绍防抖和节流的实现方式。 防抖(Debounce&am…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
