【代码随想录训练营第42期 Day45打卡 - 编辑距离问题 - LeetCode 115.不同的子序列 583. 两个字符串的删除操作 72. 编辑距离

2024-08-31 21:04
文章标签 leetcode 随想录 代码 问题 操作 字符串 距离 打卡 删除 编辑 42 训练营 序列 两个 不同 583 72 115 day45

本文主要是介绍【代码随想录训练营第42期 Day45打卡 - 编辑距离问题 - LeetCode 115.不同的子序列 583. 两个字符串的删除操作 72. 编辑距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、编辑距离问题总结

二、题目与题解

题目一：115.不同的子序列

题目链接

题解：动态规划

题目二：583. 两个字符串的删除操作

题目链接

题解1：最长公共子序列变形

题解2：编辑问题模板

题目三：72. 编辑距离

题目链接

题解：动态规划

 三、小结

一、编辑距离问题总结

编辑距离问题是动态规划算法的一个重要应用，这类问题以 72. 编辑距离 - 力扣（LeetCode）最为经典。

这里对这类问题的处理做一个步骤上的小结（以 72.编辑距离为基准）：

1. 定义dp数组

        定义一个二维数组dp，其中dp[i][j]表示字符串s1的前i个字符转换成字符串s2的前j个字符所需的最小编辑距离。

2. dp数组状态初始化

        dp[0][j]：表示空字符串转换为s2的前j个字符，需要j次插入操作。

        dp[i][0]：表示s1的前i个字符转换为空字符串，需要i次删除操作。

3. 状态转移方程

对于dp[i][j]，我们考虑s1[i-1]和s2[j-1]（即s1的第i个字符和s2的第j个字符）的匹配情况：

如果匹配：s1[i-1] == s2[j-1]，则无需编辑，dp[i][j] = dp[i-1][j-1]。

如果不匹配：s1[i-1] != s2[j-1]，则需要考虑以下三种操作，并取最小值：

        插入：在s1中插入一个字符以匹配s2[j-1]，dp[i][j] = dp[i][j-1] + 1。

        删除：删除s1中的字符s1[i-1]，dp[i][j] = dp[i-1][j] + 1。

        替换：将s1中的字符s1[i-1]替换为s2[j-1]，dp[i][j] = dp[i-1][j-1] + 1。

4. 遍历顺序

动态规划的顺序是从左到右，从上到下计算dp数组。 -- 正序

5. 返回结果

最终，dp[s1.length()][s2.length()]将给出将整个s1转换为s2所需的最小编辑距离。

这便是对于这类问题的小结，其实也是对于今天打卡题目 72. 编辑距离 - 力扣（LeetCode）的小结。我们在处理这类问题的时候可以按照这样的思路进行。

二、题目与题解

题目一：115.不同的子序列

题目链接

115. 不同的子序列 - 力扣（LeetCode）

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案
。
rabbbit
rabbbit
rabbbit

示例 2：

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

提示：

  • 1 <= s.length, t.length <= 1000
  • s 和 t 由英文字母组成
题解：动态规划

这题和昨天打卡的 392. 判断子序列 - 力扣（LeetCode）相似。

昨天思路就按照上边总结的即可。

这里需要清楚状态方程的确立：

1.当前字符匹配（s[i - 1] 与 t[j - 1]），有两种情况 -- 这里求个数，即两种情况都得考虑：

                （1）.不选择s[i-1]，则子序列个数dp[i-1][j]

                （2）.选择s[i-1]，则子序列个数dp[i-1][j-1] -- 注意：这里是针对子序列的个数，而不是长度，在原有基础上多选择一个元素，个数不变，不用+1

2.当前字符不匹配，忽略（跳过）s当前字符 -- 昨天的打卡已经提到。

状态方程如下：

                if (s[i - 1] == t[j - 1]) {    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];}else {            //当前字符不匹配，忽略（跳过）s当前字符dp[i][j] = dp[i - 1][j];

这题还需要注意一个点：题目要求结果对 109 + 7 取模 ，但实际上最后是给数据开的足够大即可，我们对于 dp 数组开 unsigned long long 就行。

完整代码如下：

class Solution {
public:int numDistinct(string s, string t) {int n = s.size();int m = t.size();if (n < m) {          //子序列不可能长度更大return 0;}vector<vector<unsigned long long>> dp(n + 1, vector<unsigned long long>(m + 1, 0));   //dp[i][j]：以i-1为结尾的s子序列（s的前i个字符）中出现以j-1为结尾的t（t的前j个字符）的个数为dp[i][j]for(int i = 0; i <= n; i++) {       //初始化dp数组：当t为空字符串时，s中有1种方式匹配（即不选择任何字符）dp[i][0] = 1;} for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {//当前字符匹配（s[i - 1] 与 t[j - 1]），有两种情况 -- 这里求个数，即两种情况都得考虑：//1.不选择s[i-1]，则子序列个数dp[i-1][j]//2.选择s[i-1]，则子序列个数dp[i-1][j-1] -- 注意：这里是针对子序列的个数，而不是长度，在原有基础上多选择一个元素，个数不变，不用+1if (s[i - 1] == t[j - 1]) {    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];}else {            //当前字符不匹配，忽略（跳过）s当前字符dp[i][j] = dp[i - 1][j];}}}return dp[n][m];}
};

题目二：583. 两个字符串的删除操作

题目链接

583. 两个字符串的删除操作 - 力扣（LeetCode）

给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

示例 1：

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例  2:

输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

  • 1 <= word1.length, word2.length <= 500
  • word1 和 word2 只包含小写英文字母
题解1：最长公共子序列变形

我们之前打卡过 1143. 最长公共子序列 - 力扣（LeetCode） 这一道题。

而现在这一道题其实就可以理解为之前那道的变形：题目通过删除元素使两者相同且使删除的步数最少，那么我们可以发现完成删除元素之后即是原来两个字符串的最长公共子序列 -- 这时，最小步数就为：两单词的长度和 - 2 * 最长公共子序列长度。

理清题意后，这题就简单了：

class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size();int m = word2.size();//求最长公共子序列长度：dp[n][m]vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));       //dp[i][j]：word1 前 i 个字符（0, i-1）与 word2 前 j 个字符（0, j-1）的最长公共子序列的长度for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; 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 n + m - 2*dp[n][m];  //最小步数：(n - dp[n][m]) + (m - dp[n][m])}
};
题解2：编辑问题模板

这里其实就跟上边总结的内容几乎一致。

需要理解的一个点就是：word1 插入一个元素等价于 word2 删除一个元素，这里只有删除操作，但完全可以按照删除和插入两个操作来看，这样基本就和总结的模板差不多。

对于字符不匹配时，有以下几种情况：

         1.删除word1[i - 1]，最少操作次数为dp[i - 1][j] + 1

         2.删除word2[j - 1]，最少操作次数为dp[i][j - 1] + 1

         3.同时删除word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2 -- 情况3实则被包含在前两种情况内，且步数更多，故取最小步数时，可以不考虑

代码如下：

class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size();int m = word2.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));   //dp[i][j]：以i-1为结尾（前 i 个元素）的字符串word1，和以j-1为结尾（前 j 个元素）的字符串word2，想要达到相等，所需要删除元素的最小步数//初始化dp数组for (int i = 1; i <= n; i++) {  //当word2为空字符串时，将word1转换为word2需要删除i个字符 -- 全部删掉dp[i][0] = i;}for (int j = 1; j <= m; j++) {      //当word1为空字符串时，将word2转换为word1需要删除j个字符 -- 全部删掉dp[0][j] = j;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (word1[i - 1] == word2[j - 1]) {         //当前字符匹配（相同），则无需删除dp[i][j] = dp[i - 1][j - 1];} //当前字符不匹配（不同）时，删除元素共有3种情况：//  1.删除word1[i - 1]，最少操作次数为dp[i - 1][j] + 1//  2.删除word2[j - 1]，最少操作次数为dp[i][j - 1] + 1//  3.同时删除word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2 -- 情况3实则被包含在前两种情况内，且步数更多，故取最小步数时，可以不考虑else {     dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);}}}return dp[n][m];}
};

题目三：72. 编辑距离

题目链接

72. 编辑距离 - 力扣（LeetCode）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成
题解：动态规划

这就是总结的经典模板题，重点就是删除，插入，替换三个操作的使用。

代码如下（含详细注释）：

class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size();int m = word2.size();vector<vector<int>> dp(n + 1,vector<int>(m + 1, 0));    //dp[i][j]：以i-1为结尾（前 i 个元素）的字符串word1，和以j-1为结尾（前 j 个元素）的字符串word2，想要达到相等，所需要操作的最小步数/*  初始化dp数组  */for (int i = 1; i <= n; i++) {              //word2为空时，word1删除当前所有元素（i）转换为word2dp[i][0] = i;}for (int j = 1; j <= m; j++) {      //word1为空时，word2删除当前所有元素（j）转换为word1dp[0][j] = j;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (word1[i - 1] == word2[j - 1]) {         //当前字符匹配，则无需编辑dp[i][j] = dp[i - 1][j - 1];}/*当前字符不匹配，有三种情况：1.删除word1[i - 1]，即dp[i - 1][j] + 1 -- 等价于在word2中插入元素word1[i - 1] 2.删除word2[j - 1]，即dp[i][j - 1] + 1 -- 等价于在word1中插入元素word2[j - 1]3.替换word1的第i个字符 word1[i - 1] 与 word2的第j个字符 word2[j - 1]，即dp[i - 1][j - 1] + 1取三者最小值，即是最小操作数*/else {dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));}}}return dp[n][m];}
};

 三、小结

昨天比较忙，今天是补的昨天的打卡，后边会继续坚持练习并打卡。

这篇关于【代码随想录训练营第42期 Day45打卡 - 编辑距离问题 - LeetCode 115.不同的子序列 583. 两个字符串的删除操作 72. 编辑距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1124990。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
2. c#从不同cs的文件调用函数

2. c#从不同cs的文件调用函数

1.文件目录如下： 2. Program.cs文件的主函数如下 using System;using System.Collections.Generic;using System.Linq;using System.Threading.Tasks;using System.Windows.Forms;namespace datasAnalysis{internal static
阅读更多...
电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

在日常使用电脑的过程中，我们经常会遇到这样的情况：一不小心，桌面上的某个重要文件被删除了。这时，大多数人可能会感到惊慌失措，不知所措。 其实，不必过于担心，因为有很多方法可以帮助我们找回被删除的桌面文件。下面，就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件，并且还没有进行其他操作，那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
活用c4d官方开发文档查询代码

活用c4d官方开发文档查询代码

当你问AI助手比如豆包，如何用python禁止掉xpresso标签时候，它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来
阅读更多...
购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点： 平衡精度 平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...
uva 10061 How many zero's and how many digits ?（不同进制阶乘末尾几个0）+poj 1401

uva 10061 How many zero's and how many digits ?（不同进制阶乘末尾几个0）+poj 1401

题意是求在base进制下的 n！的结果有几位数，末尾有几个0。 想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零，以及之前有做过的一道n阶乘的位数。 当时都是在10进制下的。 10进制下的做法是： 1. n阶位数：直接 lg（n！）就是得数的位数。 2. n阶末尾0的个数：由于2 * 5 将会在得数中以0的形式存在，所以计算2或者计算5，由于因子中出现5必然出现2，所以直接一
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2