【代码随想录训练营第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。

相关文章

MybatisGenerator文件生成不出对应文件的问题

MybatisGenerator文件生成不出对应文件的问题

《MybatisGenerator文件生成不出对应文件的问题》本文介绍了使用MybatisGenerator生成文件时遇到的问题及解决方法,主要步骤包括检查目标表是否存在、是否能连接到数据库、配置生成... 目录MyBATisGenerator 文件生成不出对应文件先在项目结构里引入“targetProje
阅读更多...
Linux使用fdisk进行磁盘的相关操作

Linux使用fdisk进行磁盘的相关操作

《Linux使用fdisk进行磁盘的相关操作》fdisk命令是Linux中用于管理磁盘分区的强大文本实用程序,这篇文章主要为大家详细介绍了如何使用fdisk进行磁盘的相关操作,需要的可以了解下... 目录简介基本语法示例用法列出所有分区查看指定磁盘的区分管理指定的磁盘进入交互式模式创建一个新的分区删除一个存
阅读更多...
C#使用HttpClient进行Post请求出现超时问题的解决及优化

C#使用HttpClient进行Post请求出现超时问题的解决及优化

《C#使用HttpClient进行Post请求出现超时问题的解决及优化》最近我的控制台程序发现有时候总是出现请求超时等问题,通常好几分钟最多只有3-4个请求,在使用apipost发现并发10个5分钟也... 目录优化结论单例HttpClient连接池耗尽和并发并发异步最终优化后优化结论我直接上优化结论吧，
阅读更多...
Golang操作DuckDB实战案例分享

Golang操作DuckDB实战案例分享

《Golang操作DuckDB实战案例分享》DuckDB是一个嵌入式SQL数据库引擎,它与众所周知的SQLite非常相似,但它是为olap风格的工作负载设计的,DuckDB支持各种数据类型和SQL特性... 目录DuckDB的主要优点环境准备初始化表和数据查询单行或多行错误处理和事务完整代码最后总结Duck
阅读更多...
Java内存泄漏问题的排查、优化与最佳实践

Java内存泄漏问题的排查、优化与最佳实践

《Java内存泄漏问题的排查、优化与最佳实践》在Java开发中,内存泄漏是一个常见且令人头疼的问题,内存泄漏指的是程序在运行过程中,已经不再使用的对象没有被及时释放,从而导致内存占用不断增加,最终... 目录引言1. 什么是内存泄漏？常见的内存泄漏情况2. 如何排查 Java 中的内存泄漏？2.1 使用 J
阅读更多...
Java 字符数组转字符串的常用方法

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu
阅读更多...
python实现pdf转word和excel的示例代码

python实现pdf转word和excel的示例代码

《python实现pdf转word和excel的示例代码》本文主要介绍了python实现pdf转word和excel的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、引言二、python编程1，PDF转Word2，PDF转Excel三、前端页面效果展示总结一
阅读更多...
java脚本使用不同版本jdk的说明介绍

java脚本使用不同版本jdk的说明介绍

《java脚本使用不同版本jdk的说明介绍》本文介绍了在Java中执行JavaScript脚本的几种方式,包括使用ScriptEngine、Nashorn和GraalVM,ScriptEngine适用... 目录Java脚本使用不同版本jdk的说明1.使用ScriptEngine执行javascript2.
阅读更多...
在MyBatis的XML映射文件中＜trim＞元素所有场景下的完整使用示例代码

在MyBatis的XML映射文件中＜trim＞元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中＜trim＞元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中，<trim>元素用于动态地添加SQL语句的一部分，例如SET或W
阅读更多...
C# 读写ini文件操作实现

C# 读写ini文件操作实现

《C#读写ini文件操作实现》本文主要介绍了C#读写ini文件操作实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录一、INI文件结构二、读取INI文件中的数据在C#应用程序中，常将INI文件作为配置文件，用于存储应用程序的
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2