算法打卡day48|动态规划篇16| Leetcode 583. 两个字符串的删除操作、72. 编辑距离

本文主要是介绍算法打卡day48|动态规划篇16| Leetcode 583. 两个字符串的删除操作、72. 编辑距离,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 算法题

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

题目链接:583. 两个字符串的删除操作

大佬视频讲解:583. 两个字符串的删除操作视频讲解

 个人思路 

本题和115.不同的子序列相比,变为了两个字符串都可以删除,整体思路是不变的,依旧用动态规划解决,关键在于递推公式的推导

解法
动态规划

动规五部曲:

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

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

2.确定递推公式

分为以下两种情况

  1. 当word1[i - 1] 与 word2[j - 1]相同的时候

  2. 当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]的话同理

4.确定遍历顺序

从递推公式 可以看出dp[i][j]都是根据左上方、正上方、正左方推出来的

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

5.举例推导dp数组

以word1:"sea",word2:"eat"为例,推导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;//初始化dp数组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()];}
}

时间复杂度:O(n*m);( n 和 m 分别为word1和 word2 的长度)

空间复杂度:O( n*m);(二维dp数组)


 Leetcode  72. 编辑距离

题目链接:72. 编辑距离

大佬视频讲解:72. 编辑距离视频讲解

个人思路

感觉思路没有打开

解法
动态规划

编辑距离是用动规来解决的经典题目,用动规可以很巧妙的算出最少编辑距离。

动规五部曲:

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

dp[i][j] 表示以下标i-1为结尾的字符串word1,和以下标j-1为结尾的字符串word2,最近编辑距离为dp[i][j]

2. 确定递推公式

在整个动规的过程中,最为关键就是正确理解dp[i][j]的定义!在确定递推公式的时候,首先要考虑清楚编辑的几种操作,也就是如下的4种情况:

if (word1[i - 1] == word2[j - 1])不操作
if (word1[i - 1] != word2[j - 1])增删换

if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑,dp[i][j] 就应该是 dp[i - 1][j - 1],即dp[i][j] = dp[i - 1][j - 1];

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;

其中word2添加一个元素,相当于word1删除一个元素,例如 word1 = "ad" ,word2 = "a"word1删除元素'd' 和 word2添加一个元素'd',变成word1="a", word2="ad"最终的操作数是一样! dp数组如下图所示意的:

            a                         a     d+-----+-----+             +-----+-----+-----+|  0  |  1  |             |  0  |  1  |  2  |+-----+-----+   ===>      +-----+-----+-----+a |  1  |  0  |           a |  1  |  0  |  1  |+-----+-----+             +-----+-----+-----+d |  2  |  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;

3. dp数组如何初始化

dp[i][0] :以下标i-1为结尾的字符串word1,和空字符串word2,最近编辑距离为dp[i][0]。

那么dp[i][0]就应该是i,对word1里的元素全部做删除操作,即:dp[i][0] = i;

同理dp[0][j] = j;

4. 确定遍历顺序

从如下四个递推公式:

  • dp[i][j] = dp[i - 1][j - 1]
  • dp[i][j] = dp[i - 1][j - 1] + 1
  • dp[i][j] = dp[i][j - 1] + 1
  • dp[i][j] = dp[i - 1][j] + 1

可以看出dp[i][j]是依赖左方,上方和左上方元素的,如图:

所以在dp矩阵中一定是从左到右从上到下去遍历。

5. 举例推导dp数组

以示例1为例,输入:word1 = "horse", word2 = "ros"为例,dp矩阵状态图如下:

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];}
}

时间复杂度:O(n*m);( n 和 m 分别为word1 和 word2 的长度)

空间复杂度:O( n*m);(二维dp数组)


 以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网

这篇关于算法打卡day48|动态规划篇16| Leetcode 583. 两个字符串的删除操作、72. 编辑距离的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/913497

相关文章

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》:本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务,增加、删

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

redis过期key的删除策略介绍

《redis过期key的删除策略介绍》:本文主要介绍redis过期key的删除策略,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录第一种策略:被动删除第二种策略:定期删除第三种策略:强制删除关于big key的清理UNLINK命令FLUSHALL/FLUSHDB命

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》:本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

Python 中的 with open文件操作的最佳实践

《Python中的withopen文件操作的最佳实践》在Python中,withopen()提供了一个简洁而安全的方式来处理文件操作,它不仅能确保文件在操作完成后自动关闭,还能处理文件操作中的异... 目录什么是 with open()?为什么使用 with open()?使用 with open() 进行

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各