代码随想录算法训练营第五十五天|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. 两个字符串的删除操作 题目链接:两个字符串的删除操作 题目描述: 给定两个单词 word1 和 word2 ,返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 解题思路: 1、确定dp数组&#x…...
Softmax 回归 + 损失函数 + 图片分类数据集【动手学深度学习v2】李沐动手学深度学习课程笔记
目录 Softmax回归 损失函数 图片分类数据集 Softmax回归从零开始实现 Softmax回归简洁实现 Softmax回归 回归和分类的区别 回归问题举例上节课的预测房价问题,分类问题就是对样本进行分类 回归和分类的具体区别 假设真实的类别为第i个类别(值为1&#x…...
git 初始化项目并上传到github
如果还没配置过,需要配置账号信息 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对象操作技巧,全场景解析
✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 所属的专栏:前端泛海 景天的主页:景天科技苑 文章目录 1.js的DOM介绍2.节点元素层级关系3.通过js修改,清空节点…...
TCP包头、TCP为什么安全可靠、UDP和TCP的区别、http协议
我要成为嵌入式高手之3月8日Linux高编第十八天!! __________________________________________________ 学习笔记 TPC包头 1、序号 发送端发送数据包的编号 2、确认号 已经确认接收到的数据的编号,只有当ACK为1时,该位才有用 …...
Android使用WebView打开内嵌H5网页
Android打开外部网页链接请参考上一篇文章 https://public.blog.csdn.net/article/details/136384559 继上篇,新建assets文章夹,将H5的网页资源放到此文件夹下 把H5的资源文件都拷进来 这个时候,将添加打开本地网页的代码: //打…...
UDP实现文件的发送、UDP实现全双工的聊天、TCP通信协议
我要成为嵌入式高手之3月7日Linux高编第十七天!! ———————————————————————————— 回顾 重要程序 1、UDP实现文件的发送 发端: #include "head.h"int main(void) {int sockfd 0;struct sockaddr_i…...
Yocto - Project Quick Build
欢迎光临! 这篇简短的文档将向您介绍使用 Yocto 项目构建典型镜像的过程。本文还介绍了如何为特定硬件配置构建。您将使用 Yocto Project 构建一个名为 Poky 的参考嵌入式操作系统。 Welcome! This short document steps you through the process for a typical i…...
深入探讨C++中的可变参数列表(Variadic Templates)
文章目录 导言可变参数列表的基本用法使用std::initializer_list应用场景 导言 在C编程中,处理可变数量参数的能力是一种非常有用的功能。通过可变参数列表,你可以编写更加通用和灵活的函数,从而提高代码的可读性和重用性。本文将详细介绍C中…...
MS2548 国产自动方向控制、半双工 RS-485 收发器 替代MAX13487
MS2548 国产自动方向控制、半双工 RS-485 收发器 替代MAX13487 北京冠宇铭通科技有限公司 肖小姐 产品简述 MS2548 是一个 5V 供电、半双工 RS-485 收发器。 芯片具有自动换向控制功能,可用于隔离485 端口,驱动器输入与使能信号一起配合控制芯片的状态&…...
数据库大师之路:Oracle在线学习平台全指南!
介绍数据库是由甲骨文公司开发的一款关系数据库管理系统(RDBMS),在数据库领域具有领先地位,并且以其系统可移植性而闻名。以下是对Oracle数据库的详细介绍: 市场地位: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. 前言 随着移动智能设备的普及,各种各样的使用需求也被开发出来&…...
华为北向网管NCE开发教程(3)CORBA协议开发
华为北向网管NCE开发教程(1)闭坑选接口协议 华为北向网管NCE开发教程(2)REST接口开发 华为北向网管NCE开发教程(3)CORBA协议开发 如果你真的还有选择的余地,能用REST,尽量用REST&…...
【算法训练营】最长公共子序列,倒水问题,奶牛吃草(Python实现)
最长公共子序列 时间限制:1 sec 空间限制:256 MB 问题描述 给定两个 1 到 n 的排列 A,B (即长度为 n 的序列,其中 [1,n] 之间的所有数都出现了恰好一次)。 求它们的最长公共子序列长度。 输入格式 第一行一个整数 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运算符: − * % / ! < > <…...
【守护健康】小脑萎缩患者必备营养指南
当生活给予我们挑战,我们选择用科学和关爱予以回应。面对小脑萎缩这一难题,正确的营养补充不仅是一剂强心针,更是患者康复之路上的坚实伙伴。今天,让我们一起了解那些能够助力小脑萎缩患者的神奇维生素! 1. 维生素B群…...
lvs集群中NAT模式
群集的含义 由多台主机构成,但对外表现为一个整体,只提供一个访问入口,相当于一台大型的计算机。 横向发展:放更多的服务器,有调度分配的问题。 垂直发展:升级单机的硬件设备,提高单个服务器自身功能。 …...
FPGA——三速自适应以太网设计(2)GMII与RGMII接口
FPGA——以太网设计(2)GMII与RGMII 基础知识(1)GMII(2)RGMII(3)IDDR GMII设计转RGMII接口跨时钟传输模块 基础知识 (1)GMII GMII:发送端时钟由MAC端提供 下…...
【校园导航小程序】2.0版本 静态/云开发项目 升级日志
演示视频 【校园导航小程序】2.0版本 静态/云开发项目 演示 首页 重做了首页,界面更加高效和美观 校园指南页 新增了 “校园指南” 功能,可以搜索和浏览校园生活指南 地图页 ①弃用路线规划插件,改用SDK开发包。可以无阻通过审核并发布…...
深入揭秘Lucene:全面解析其原理与应用场景(二)
本系列文章简介: 本系列文章将深入揭秘Lucene,全面解析其原理与应用场景。我们将从Lucene的基本概念和核心组件开始,逐步介绍Lucene的索引原理、搜索算法以及性能优化策略。通过阅读本文,读者将会对Lucene的工作原理有更深入的了解…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
