当前位置: 首页 > 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的工作原理有更深入的了解…...

【C# .NET 11 AI推理加速实战指南】:3大GPU绑定陷阱、5种ONNX Runtime优化配置、11个真实报错代码级修复方案

第一章&#xff1a;C# .NET 11 AI推理加速报错解决方法总览 在 C# .NET 11 中集成 ONNX Runtime 或 ML.NET 进行 AI 模型推理时&#xff0c;常因运行时环境、本机依赖或 API 兼容性问题引发异常&#xff0c;如 DllNotFoundException、 InvalidDataException&#xff08;ONNX 图…...

微信生态的技术引擎API

本文为介绍WTAPI微信开发解决方案的核心价值与应用实践 一、微信生态的崛起与挑战 在数字化时代&#xff0c;微信已成为连接用户与企业的重要桥梁。随着微信生态的不断发展&#xff0c;企业对微信能力的需求也日益增长。然而&#xff0c;企业在接入微信能力时面临着诸多挑战&a…...

Anthropic新品频发致传统软件股暴跌,AI与SaaS融合能否成未来趋势?

Anthropic新品频发引发行业震荡&#xff1a;传统软件股暴跌&#xff0c;AI与SaaS融合成未来趋势&#xff1f;又一家明星公司&#xff0c;被Anthropic无情“斩杀”。4月18日&#xff0c;Anthropic发布新产品Claude Design。用户能通过它创建网页或App设计方案&#xff0c;涵盖交…...

python circleci

## 聊聊 Python 项目中的 CircleCI&#xff1a;一个持续集成工具的日常 如果你在团队里写过一段时间 Python&#xff0c;尤其是参与过需要多人协作、频繁更新的项目&#xff0c;大概会对这样一些场景感到熟悉&#xff1a;代码刚合并到主分支&#xff0c;某个之前运行得好好的功…...

057.YOLOv5代码调试技巧:用VSCode/PyCharm给深度学习“把脉”

最近在项目里遇到一个诡异的问题:YOLOv5训练时loss曲线看着挺正常,但验证集mAP就是上不去。模型推理时偶尔还会出现框位置漂移,像是特征图对齐出了问题。这种时候,光靠print和猜是没用的,得上调试器——就像给代码做一次深度CT扫描。 从一次真实调试经历说起 那天晚上十…...

避坑指南:不是所有MATLAB程序都适合用GPU加速,这4类情况要小心

GPU加速MATLAB的四大陷阱&#xff1a;如何避免性能反降&#xff1f; 最近在帮同事优化一个图像处理项目时&#xff0c;遇到了典型的GPU加速困境——原本期待3-5倍的性能提升&#xff0c;实际测试却只快了不到20%&#xff0c;某些参数下甚至比CPU版本更慢。这让我意识到&#xf…...

HsMod插件终极指南:55项功能详解与快速上手教程

HsMod插件终极指南&#xff1a;55项功能详解与快速上手教程 【免费下载链接】HsMod Hearthstone Modification Based on BepInEx 项目地址: https://gitcode.com/GitHub_Trending/hs/HsMod HsMod是一款基于BepInEx框架开发的《炉石传说》增强插件&#xff0c;为玩家提供…...

WinClaw安全实战 10|5分钟微信接入指南:零代码远程操控电脑,AI助手随身带

摘要:前9篇专栏已让WinClaw具备Office自动化、浏览器控制、零脚本测试等强大本地能力,但“必须坐在电脑前操作”的物理限制始终存在。本文作为“多渠道消息对接与远程操控”模块开篇,聚焦微信ClawBot官方接入方案——通过“安装插件→启动服务→扫码绑定”三步零代码操作,5…...

Flink+SLS 云原生组合:构建阿里云 OpenAPI 网关实时监控体系,故障发现提速至秒级!

背景与挑战阿里云开放平台&#xff08;OpenAPI&#xff09;是开发者管理云上资源的标准入口&#xff0c;承载了几乎所有云产品的对外接口&#xff0c;满足客户自动化运维与云资源管控的核心诉求。随着企业对自动化的依赖日益加深&#xff0c;OpenAPI 的稳定性建设变得至关重要。…...

VCS仿真器下UVM调试实战:手把手解决uvm_hdl_force权限与$urandom_range范围溢出

VCS仿真器下UVM调试实战&#xff1a;手把手解决uvm_hdl_force权限与$urandom_range范围溢出 在芯片验证领域&#xff0c;UVM&#xff08;Universal Verification Methodology&#xff09;已成为事实上的标准。然而&#xff0c;当我们在Synopsys VCS这样的商业仿真器上实现UVM验…...