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

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...

Qt的学习(一)

1.什么是Qt Qt特指用来进行桌面应用开发&#xff08;电脑上写的程序&#xff09;涉及到的一套技术Qt无法开发网页前端&#xff0c;也不能开发移动应用。 客户端开发的重要任务&#xff1a;编写和用户交互的界面。一般来说和用户交互的界面&#xff0c;有两种典型风格&…...