day56补

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

力扣题目链接(opens new window)

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

示例:

  • 输入: "sea", "eat"
  • 输出: 2
  • 解释: 第一步将"sea"变为"ea",第二步将"eat"变为"ea"

#算法公开课

《代码随想录》算法视频公开课 (opens new window):LeetCode:583.两个字符串的删除操 (opens new window),相信结合视频再看本篇题解,更有助于大家对本题的理解

#思路

#动态规划一

本题和动态规划:115.不同的子序列 (opens new window)相比,其实就是两个字符串都可以删除了,情况虽说复杂一些,但整体思路是不变的。

这次是两个字符串可以相互删了,这种题目也知道用动态规划的思路来解,动规五部曲,分析如下:

  1. 确定dp数组(dp table)以及下标的含义

dp[i][j]:以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等,所需要删除元素的最少次数。

这里dp数组的定义有点点绕,大家要撸清思路。

  1. 确定递推公式
  • 当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。

  1. dp数组如何初始化

从递推公式中,可以看出来,dp[i][0] 和 dp[0][j]是一定要初始化的。

dp[i][0]:word2为空字符串,以i-1为结尾的字符串word1要删除多少个元素,才能和word2相同呢,很明显dp[i][0] = i。

dp[0][j]的话同理,所以代码如下:

vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;

1
2
3

  1. 确定遍历顺序

从递推公式 dp[i][j] = min(dp[i - 1][j - 1] + 2, min(dp[i - 1][j], dp[i][j - 1]) + 1); 和dp[i][j] = dp[i - 1][j - 1]可以看出dp[i][j]都是根据左上方、正上方、正左方推出来的。

所以遍历的时候一定是从上到下,从左到右,这样保证dp[i][j]可以根据之前计算出来的数值进行计算。

  1. 举例推导dp数组

以word1:"sea",word2:"eat"为例,推导dp数组状态图如下:

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

以上分析完毕,代码如下:

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;for (int i = 1; i <= word1.size(); i++) {for (int j = 1; j <= word2.size(); j++) {if (word1[i - 1] == word2[j - 1]) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);}}}return dp[word1.size()][word2.size()];}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

  • 时间复杂度: O(n * m)
  • 空间复杂度: O(n * m)

#动态规划二

本题和动态规划:1143.最长公共子序列 (opens new window)基本相同,只要求出两个字符串的最长公共子序列长度即可,那么除了最长公共子序列之外的字符都是必须删除的,最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

代码如下:

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));for (int i=1; i<=word1.size(); i++){for (int j=1; j<=word2.size(); j++){if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}return word1.size()+word2.size()-dp[word1.size()][word2.size()]*2;}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

  • 时间复杂度: O(n * m)
  • 空间复杂度: O(n * m)

#其他语言版本

#Java:

// dp数组中存储word1和word2最长相同子序列的长度
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;}
}// dp数组中存储需要删除的字符个数
class Solution {public int minDistance(String word1, String word2) {int[][] dp = new int[word1.length() + 1][word2.length() + 1];for (int i = 0; i < word1.length() + 1; i++) dp[i][0] = i;for (int j = 0; j < word2.length() + 1; j++) dp[0][j] = j;for (int i = 1; i < word1.length() + 1; i++) {for (int j = 1; j < word2.length() + 1; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];}else{dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));}}}return dp[word1.length()][word2.length()];}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

//DP - longest common subsequence (用最長公共子序列反推)
class Solution {public int minDistance(String word1, String word2) {char[] char1 = word1.toCharArray();char[] char2 = word2.toCharArray();int len1 = char1.length;int len2 = char2.length;int dp[][] = new int [len1 + 1][len2 + 1];for(int i = 1; i <= len1; i++){for(int j = 1; j <= len2; j++){if(char1[i - 1] == char2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}return len1 + len2 - (2 * dp[len1][len2]);//和leetcode 1143只差在這一行。}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/130468.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

GcExcel:Java 应用创建、修改和保存 Excel 电子表格 -Crack

在 Java 应用程序中创建、修改和保存 Excel 电子表格&#xff1a; GrapeCity Documents for Excel&#xff0c;Java 版 (GcExcel) 是一个高速 Java Excel 电子表格 API 库&#xff0c;不需要依赖于 Microsoft Excel。用户可以通过 Java 应用程序以编程方式创建、编辑、导入和导…

2020-2022年低纬高原区典型种养殖区氮磷干湿沉降数据集

摘要 氮磷干湿沉降是指大气中氮磷通过沉降方式到达地面,进入陆地生态系统物质循环的过程,干湿沉降在环境氮磷污染输入中占据重要比例。我国是种养殖业大国,摸清源于种植业和养殖业氮磷干湿沉降负荷,对评估氮磷干湿沉降生态效应,指导环境污染治理,促进种养殖业绿色发展具有…

无涯教程-JavaScript - PMT函数

描述 PMT功能基于固定的还款额和固定的利率来计算贷款的还款额。 语法 PMT (rate, nper, pv, [fv], [type])争论 Argument描述Required/OptionalRateThe interest rate for the loan.RequiredNperThe total number of payments for the loan.RequiredPv 现在的价值,或一系列…

一个患有精神分裂症程序员,用10年写了一个“拯救世界”的操作系统

操作系统是一个极其复杂的软件&#xff0c;一个人开发的话工作量特别吓人。 但是一个患有精神分裂症的天才程序员Terry Davis&#xff0c;宣称接到了来自上帝的指示&#xff1a;你要建立一座神庙&#xff0c;用操作系统的方式。 于是&#xff0c;Terry整整花了10年时间&#x…

Python经典小游戏02:字母数字代码雨

★★★★★博文创作不易&#xff0c;我的博文不需要打赏&#xff0c;也不需要知识付费&#xff0c;可以白嫖学习编程小技巧。使用代码的过程中&#xff0c;如有疑问的地方&#xff0c;欢迎大家指正留言交流。喜欢的老铁可以多多点赞收藏分享置顶&#xff0c;小红牛在此表示感谢…

系统架构设计师(第二版)学习笔记----嵌入式系统及软件

【原文链接】系统架构设计师&#xff08;第二版&#xff09;学习笔记----嵌入式系统及软件 文章目录 一、嵌入式系统1.1 嵌入式系统的组成1.2 嵌入式系统的特点1.3 嵌入式系统的分类 二、嵌入式软件2.1 嵌入式系统软件分层2.2 嵌入式软件的主要特点 三、安全攸关软件的安全性设…

【前端项目】博客系统(页面设计)

文章目录 一、预期效果二、实现博客列表页三、实现博客正文页四、实现博客登录页五、实现博客编辑页 一、预期效果 代码详情见&#xff1a;gitee链接 &#x1f495; 博客列表页效果 &#x1f495; 博客详情页效果 &#x1f495; 博客登录页效果 &#x1f495; 博客编辑页效果…

首个国家级元宇宙计划发布,和数集团迎来赛道发展新机遇

近日&#xff0c;工业和信息化部、教育部、文化和旅游部、国务院国资委、国家广播电视总局办公厅五部门联合印发《元宇宙产业创新发展三年行动计划&#xff08;2023-2025年&#xff09;》&#xff08;以下简称《计划》&#xff09;&#xff0c;其中在发展目标中提到要培育3-5家…

【C++】哈希——哈希的概念,应用以及闭散列和哈希桶的模拟实现

前言&#xff1a; 前面我们一同学习了二叉搜索树&#xff0c;以及特殊版本的平衡二叉搜索树&#xff0c;这些容器让我们查找数据的效率提高到了O(log^2 N)。虽然效率提高了很多&#xff0c;但是有没有一种理想的方法使得我们能提高到O(1)呢&#xff1f;其实在C语言数据结构中&a…

服务器数据恢复-EMC存储磁盘损坏的RAID5数据恢复案例

服务器数据恢复环境&#xff1a; 北京某单位有一台EMC某型号存储&#xff0c;有一组由10块STAT硬盘组建的RAID5阵列&#xff0c;另外2块磁盘作为热备盘使用。RAID5阵列上层只划分了一个LUN&#xff0c;分配给SUN小机使用&#xff0c;上层文件系统为ZFS。 服务器故障&#xff1…

【语义分割 01】Open MMLab介绍

1 Tutorial https://github.com/TommyZihao/MMSegmentation_Tutorials https://github.com/TommyZihao/Train_Custom_Dataset https://github.com/TommyZihao/aidlux_tutorial OpenMMLab是一个由中国开发者主导的具有世界影响力的人工智能计算机视觉开源算法体系, 至今已经开…

掌握信息利器,快速发现潜在商机——介绍一款高效的数据检索软件

掌握信息利器&#xff0c;快速发现潜在商机——介绍一款高效的数据检索软件 在当今信息爆炸的时代&#xff0c;获取准确、实时的信息变得至关重要。为了帮助您快速发现潜在商机&#xff0c;我们推出了一款功能强大的数据检索软件。无论您是市场调研人员、销售专员还是企业经营者…

花见Live Wallpaper Themes 4K Pro for mac(4k视频壁纸)

如果你希望让自己的Mac桌面焕发活力&#xff0c;那么Live Wallpaper & Themes 4K Pro正是一款值得尝试的软件。它提供了丰富的超高清4K动态壁纸和主题&#xff0c;可以让你轻松打造出个性化的桌面环境。 这款软件拥有众多令人惊叹的功能。其中最值得一提的是&#xff0c;它…

Windows下的Elasticsearch-head安装

Windows下的Elasticsearch-head安装 参考&#xff1a;https://gitcode.net/mirrors/mobz/elasticsearch-head 需要用到 npm 命令&#xff0c;这里可以提前下载安装下Node.js 即可自动安装npm&#xff1b; Node.js 下载安装地址&#xff1a;https://nodejs.org/en/download # 进…

sql server 查询某个字段是否有值 返回bool类型

sql server 查询某个字段是否有值 返回bool类型&#xff0c;true 或 false SELECT ColumnCode,CONVERT(BIT,CASE WHEN LEN(ColumnCode) > 0 THEN 1 ELSE 0 END) AS HasValue FROM dbo.TF_LessonCatalog

生物通路数据库收录1600+整合的经典通路

生物通路数据库为科学家提供了关于生物通路的大量信息和资源&#xff0c;特别是在数据整合、信息检索、数据可视化分析、数据交互、生物学研究等方面&#xff0c;积极推动了生物学研究和科学的发展。 世界各地正在创建各种类型的通路数据库&#xff0c;每个数据库都反映了其创…

【大数据】基于 Flink CDC 高效构建入湖通道

基于 Flink CDC 高效构建入湖通道 1.Flink CDC 核心技术解析2.CDC 数据入湖入仓的挑战2.1 CDC 数据入湖架构2.2 CDC 数据 ETL 架构 3.基于 Flink CDC 的入湖入仓方案3.1 Flink CDC 入湖入仓架构3.2 Flink CDC ETL 分析3.3 存储友好的写入设计3.4 Flink CDC 实现异构数据源集成3…

UI库DHTMLX Suite v8.2发布全新表单组件,让Web表单实现高度可定制!

DHTMLX Suite v8.2日前已正式发布&#xff0c;此版本的核心是DHTMLX Form&#xff0c;这个小部件接收了4个备受期待的新控件&#xff0c;如Fieldset、Avatar、Toggle和ToggleGroup。官方技术团队还为Grid和TreeGrid小部件中的页眉/页脚工具提示提供了一系列新的配置选项等。 在…

Unity和C#游戏编程入门:创建迷宫小球游戏示例

&#x1f482; 个人网站:【工具大全】【游戏大全】【神级源码资源网】&#x1f91f; 前端学习课程&#xff1a;&#x1f449;【28个案例趣学前端】【400个JS面试题】&#x1f485; 寻找学习交流、摸鱼划水的小伙伴&#xff0c;请点击【摸鱼学习交流群】 当涉及到Unity和C#游戏编…

【软件测试】Postman中变量的使用

Postman中可设置的变量类型有全局变量&#xff0c;环境变量&#xff0c;集合变量&#xff0c;数据变量及局部变量。区别则是各变量作用域不同&#xff0c;全局变量适用于所有集合&#xff0c;环境变量适用于当前所选环境&#xff08;所有集合中均可使用不同环境变量&#xff09…