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

代码随想录算法训练营第五十五天|583. 两个字符串的删除操作、72. 编辑距离。

583. 两个字符串的删除操作

题目链接:两个字符串的删除操作

题目描述
给定两个单词 word1 和 word2 ,返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。

解题思路
1、确定dp数组(dp table)以及下标的含义
dp[i][j]:以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等,所需要删除元素的最少次数。
这里dp数组的定义有点点绕,大家要撸清思路。
2、确定递推公式
当word1[i - 1] 与 word2[j - 1]相同的时候
当word1[i - 1] 与 word2[j - 1]不相同的时候
当word1[i - 1] 与 word2[j - 1]相同的时候,dp[i][j] = dp[i - 1][j - 1];
当word1[i - 1] 与 word2[j - 1]不相同的时候,有三种情况:
情况一:删word1[i - 1],最少操作次数为dp[i - 1][j] + 1
情况二:删word2[j - 1],最少操作次数为dp[i][j - 1] + 1
情况三:同时删word1[i - 1]和word2[j - 1],操作的最少次数为dp[i - 1][j - 1] + 2
那最后当然是取最小值,所以当word1[i - 1] 与 word2[j - 1]不相同的时候,递推公式:dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2,所以递推公式可简化为:dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
这里可能不少录友有点迷糊,从字面上理解 就是 当 同时删word1[i - 1]和word2[j - 1],dp[i][j-1] 本来就不考虑 word2[j - 1]了,那么我在删 word1[i - 1],是不是就达到两个元素都删除的效果,即 dp[i][j-1] + 1。
3、dp数组如何初始化
从递推公式中,可以看出来,dp[i][0] 和 dp[0][j]是一定要初始化的。
dp[i][0]:word2为空字符串,以i-1为结尾的字符串word1要删除多少个元素,才能和word2相同呢,很明显dp[i][0] = i。
dp[0][j]的话同理
代码实现

class Solution {public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1 + 1][len2 + 1];for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return len1 + len2 - dp[len1][len2] * 2;}
}

72. 编辑距离

题目链接:编辑距离

题目描述
给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符

解题思路
递推公式:
1、if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑,dp[i][j] 就应该是 dp[i - 1][j - 1],即dp[i][j] = dp[i - 1][j - 1];
2、if (word1[i - 1] != word2[j - 1]),此时就需要编辑了。
操作一:word1删除一个元素,那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] = dp[i - 1][j] + 1;
操作二:word2删除一个元素,那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] = dp[i][j - 1] + 1;
操作三:替换元素,word1替换word1[i - 1],使其与word2[j - 1]相同,此时不用增删加元素。
可以回顾一下,if (word1[i - 1] = = word2[j - 1])的时候我们的操作 是 dp[i][j] = dp[i - 1][j - 1] 对吧。
那么只需要一次替换的操作,就可以让 word1[i - 1] 和 word2[j - 1] 相同。
所以 dp[i][j] = dp[i - 1][j - 1] + 1;
综上,当 if (word1[i - 1] != word2[j - 1]) 时取最小的,即:dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
代码实现

class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 1];// 初始化for (int i = 1; i <= m; i++) {dp[i][0] = i;}for (int j = 1; j <= n; j++) {dp[0][j] = j;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 因为dp数组有效位从1开始// 所以当前遍历到的字符串的位置为i-1 | j-1if (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]), dp[i - 1][j]) + 1;}}}return dp[m][n];}
}

相关文章:

代码随想录算法训练营第五十五天|583. 两个字符串的删除操作、72. 编辑距离。

583. 两个字符串的删除操作 题目链接&#xff1a;两个字符串的删除操作 题目描述&#xff1a; 给定两个单词 word1 和 word2 &#xff0c;返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 解题思路&#xff1a; 1、确定dp数组&#x…...

Softmax 回归 + 损失函数 + 图片分类数据集【动手学深度学习v2】李沐动手学深度学习课程笔记

目录 Softmax回归 损失函数 图片分类数据集 Softmax回归从零开始实现 Softmax回归简洁实现 Softmax回归 回归和分类的区别 回归问题举例上节课的预测房价问题&#xff0c;分类问题就是对样本进行分类 回归和分类的具体区别 假设真实的类别为第i个类别&#xff08;值为1&#x…...

git 初始化项目并上传到github

如果还没配置过&#xff0c;需要配置账号信息 git config --global user.name "baymax-collab" git config --global user.email "baymax-collabtest.com"创建一个新的存储库 git clone gitgithub.com:xxxx cd test git switch --create main touch READ…...

前端javascript的DOM对象操作技巧,全场景解析

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属的专栏&#xff1a;前端泛海 景天的主页&#xff1a;景天科技苑 文章目录 1.js的DOM介绍2.节点元素层级关系3.通过js修改&#xff0c;清空节点…...

TCP包头、TCP为什么安全可靠、UDP和TCP的区别、http协议

我要成为嵌入式高手之3月8日Linux高编第十八天&#xff01;&#xff01; __________________________________________________ 学习笔记 TPC包头 1、序号 发送端发送数据包的编号 2、确认号 已经确认接收到的数据的编号&#xff0c;只有当ACK为1时&#xff0c;该位才有用 …...

Android使用WebView打开内嵌H5网页

Android打开外部网页链接请参考上一篇文章 https://public.blog.csdn.net/article/details/136384559 继上篇&#xff0c;新建assets文章夹&#xff0c;将H5的网页资源放到此文件夹下 把H5的资源文件都拷进来 这个时候&#xff0c;将添加打开本地网页的代码&#xff1a; //打…...

UDP实现文件的发送、UDP实现全双工的聊天、TCP通信协议

我要成为嵌入式高手之3月7日Linux高编第十七天&#xff01;&#xff01; ———————————————————————————— 回顾 重要程序 1、UDP实现文件的发送 发端&#xff1a; #include "head.h"int main(void) {int sockfd 0;struct sockaddr_i…...

Yocto - Project Quick Build

欢迎光临&#xff01; 这篇简短的文档将向您介绍使用 Yocto 项目构建典型镜像的过程。本文还介绍了如何为特定硬件配置构建。您将使用 Yocto Project 构建一个名为 Poky 的参考嵌入式操作系统。 Welcome! This short document steps you through the process for a typical i…...

深入探讨C++中的可变参数列表(Variadic Templates)

文章目录 导言可变参数列表的基本用法使用std::initializer_list应用场景 导言 在C编程中&#xff0c;处理可变数量参数的能力是一种非常有用的功能。通过可变参数列表&#xff0c;你可以编写更加通用和灵活的函数&#xff0c;从而提高代码的可读性和重用性。本文将详细介绍C中…...

MS2548 国产自动方向控制、半双工 RS-485 收发器 替代MAX13487

MS2548 国产自动方向控制、半双工 RS-485 收发器 替代MAX13487 北京冠宇铭通科技有限公司 肖小姐 产品简述 MS2548 是一个 5V 供电、半双工 RS-485 收发器。 芯片具有自动换向控制功能&#xff0c;可用于隔离485 端口&#xff0c;驱动器输入与使能信号一起配合控制芯片的状态&…...

数据库大师之路:Oracle在线学习平台全指南!

介绍数据库是由甲骨文公司开发的一款关系数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;在数据库领域具有领先地位&#xff0c;并且以其系统可移植性而闻名。以下是对Oracle数据库的详细介绍&#xff1a; 市场地位&#xff1a;Oracle数据库是目前世界上流行的关系数…...

如何在Windows系统部署Jellyfin Server并实现公网访问内网影音文件

文章目录 1. 前言2. Jellyfin服务网站搭建2.1. Jellyfin下载和安装2.2. Jellyfin网页测试 3.本地网页发布3.1 cpolar的安装和注册3.2 Cpolar云端设置3.3 Cpolar本地设置 4.公网访问测试5. 结语 1. 前言 随着移动智能设备的普及&#xff0c;各种各样的使用需求也被开发出来&…...

华为北向网管NCE开发教程(3)CORBA协议开发

华为北向网管NCE开发教程&#xff08;1&#xff09;闭坑选接口协议 华为北向网管NCE开发教程&#xff08;2&#xff09;REST接口开发 华为北向网管NCE开发教程&#xff08;3&#xff09;CORBA协议开发 如果你真的还有选择的余地&#xff0c;能用REST&#xff0c;尽量用REST&…...

【算法训练营】最长公共子序列,倒水问题,奶牛吃草(Python实现)

最长公共子序列 时间限制&#xff1a;1 sec 空间限制&#xff1a;256 MB 问题描述 给定两个 1 到 n 的排列 A,B &#xff08;即长度为 n 的序列&#xff0c;其中 [1,n] 之间的所有数都出现了恰好一次&#xff09;。 求它们的最长公共子序列长度。 输入格式 第一行一个整数 n &a…...

Armadillo:矩阵类、向量类、Cube类和泛型类

文章目录 矩阵类、向量类、Cube类和泛型类Mat<type>matcx_matCol<type>veccx_vecRow<type>rowveccx_rowvecCube<type>cubecx_cubefield<object_type>SpMat<type>sp_matsp_cx_mat运算符&#xff1a; − * % / &#xff01; < > <…...

【守护健康】小脑萎缩患者必备营养指南

当生活给予我们挑战&#xff0c;我们选择用科学和关爱予以回应。面对小脑萎缩这一难题&#xff0c;正确的营养补充不仅是一剂强心针&#xff0c;更是患者康复之路上的坚实伙伴。今天&#xff0c;让我们一起了解那些能够助力小脑萎缩患者的神奇维生素&#xff01; 1. 维生素B群…...

lvs集群中NAT模式

群集的含义 由多台主机构成&#xff0c;但对外表现为一个整体&#xff0c;只提供一个访问入口&#xff0c;相当于一台大型的计算机。 横向发展:放更多的服务器&#xff0c;有调度分配的问题。 垂直发展&#xff1a;升级单机的硬件设备&#xff0c;提高单个服务器自身功能。 …...

FPGA——三速自适应以太网设计(2)GMII与RGMII接口

FPGA——以太网设计&#xff08;2&#xff09;GMII与RGMII 基础知识&#xff08;1&#xff09;GMII&#xff08;2&#xff09;RGMII&#xff08;3&#xff09;IDDR GMII设计转RGMII接口跨时钟传输模块 基础知识 &#xff08;1&#xff09;GMII GMII:发送端时钟由MAC端提供 下…...

【校园导航小程序】2.0版本 静态/云开发项目 升级日志

演示视频 【校园导航小程序】2.0版本 静态/云开发项目 演示 首页 重做了首页&#xff0c;界面更加高效和美观 校园指南页 新增了 “校园指南” 功能&#xff0c;可以搜索和浏览校园生活指南 地图页 ①弃用路线规划插件&#xff0c;改用SDK开发包。可以无阻通过审核并发布…...

深入揭秘Lucene:全面解析其原理与应用场景(二)

本系列文章简介&#xff1a; 本系列文章将深入揭秘Lucene&#xff0c;全面解析其原理与应用场景。我们将从Lucene的基本概念和核心组件开始&#xff0c;逐步介绍Lucene的索引原理、搜索算法以及性能优化策略。通过阅读本文&#xff0c;读者将会对Lucene的工作原理有更深入的了解…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...