【算法与数据结构】583、72、LeetCode两个字符串的删除操作+编辑距离

文章目录

  • 一、583、两个字符串的删除操作
  • 二、72、编辑距离
  • 三、完整代码

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、583、两个字符串的删除操作

在这里插入图片描述

  思路分析：本题的思路和115、不同的子序列差不多，只是变成了两个字符串都能删除字符。

  1. 第一步，动态数组的含义。 d p [ i ] [ j ] dp[i][j] dp[i][j]代表使得 w o r d 1 [ 0 , i − 1 ] word1[0, i-1] word1[0,i−1]和 w r o d 2 [ 0 , j − 1 ] wrod2[0, j-1] wrod2[0,j−1]相等所需删除的最小步数。
  2. 第二步，递推公式。 d p [ i ] [ j ] dp[i][j] dp[i][j]可以由两种情况推导出来：
  • w o r d 1 [ i − 1 ] word1[i - 1] word1[i−1]与 w o r d 2 [ j − 1 ] word2[j - 1] word2[j−1]相同：那么最小步数和使得 w o r d 1 [ 0 , i − 2 ] word1[0, i-2] word1[0,i−2]和 w r o d 2 [ 0 , j − 2 ] wrod2[0, j-2] wrod2[0,j−2]相等所需删除的最小步数相同。 d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] dp[i][j] = dp[i-1][j-1] dp[i][j]=dp[i−1][j−1]。
  • w o r d 1 [ i − 1 ] word1[i - 1] word1[i−1]与 w o r d 2 [ j − 1 ] word2[j - 1] word2[j−1]不相同：这种情况的 d p [ i ] [ j ] dp[i][j] dp[i][j]可以由三部分构成：若 w o r d 1 [ 0 , i − 2 ] word1[0, i - 2] word1[0,i−2]和 w o r d 2 [ 0 , j − 1 ] word2[0, j - 1] word2[0,j−1]做了 d p [ i − 1 ] [ j ] dp[i - 1][j] dp[i−1][j]次删除操作以后会相等，那么再删除 w o r d 1 [ i − 1 ] word1[i - 1] word1[i−1]以后又可以相等，即 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + 1 dp[i][j] = dp[i - 1][j] + 1 dp[i][j]=dp[i−1][j]+1；若 w o r d 1 [ 0 , i − 1 ] word1[0, i - 1] word1[0,i−1]和 w o r d 2 [ 0 , j − 2 ] word2[0, j - 2] word2[0,j−2]做了 d p [ i ] [ j − 1 ] dp[i][j - 1] dp[i][j−1]次删除操作以后会相等，那么再删除 w o r d 2 [ j − 1 ] word2[j - 1] word2[j−1]以后又可以相等，即 d p [ i ] [ j ] = d p [ i ] [ j − 1 ] + 1 dp[i][j] = dp[i][j - 1] + 1 dp[i][j]=dp[i][j−1]+1。因为要求最小步数，那么我们对两项取最小： d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j ] + 1 , d p [ i ] [ j − 1 ] + 1 ) dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1) dp[i][j]=min(dp[i−1][j]+1,dp[i][j−1]+1)。
	if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];else dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
  1. 第三步，元素初始化。 d p [ i ] [ 0 ] dp[i][0] dp[i][0]（第一列）表示字符串 w o r d 1 [ 0 , i − 1 ] word1[0, i-1] word1[0,i−1]变成空字符串需要删除的最小字符个数。 d p [ 0 ] [ j ] dp[0][j] dp[0][j]（第一行）表示 w o r d 2 [ 0 , j − 1 ] word2[0, j-1] word2[0,j−1]变成空字符串需要删除的最小字符个数。其中，空字符串word1变成空字符串word2的个数为0。那么 d p [ 0 ] [ 0 ] = 0 , d p [ i ] [ 0 ] = i , d p [ 0 ] [ j ] = j dp[0][0]=0, dp[i][0] = i, dp[0][j] = j dp[0][0]=0,dp[i][0]=i,dp[0][j]=j。
		for (int i = 1; i <= word1.size(); i++) dp[i][0] = i;		// 第一列初始化为ifor (int j = 1; j <= word2.size(); j++) dp[0][j] = j;		// 第一行初始化为i
  1. 第四步，递归顺序。一共有两层循环，从前往后进行遍历。
  2. 第五步，打印结果。

在这里插入图片描述

  程序如下：

// 583、两个字符串的删除操作-动态规划
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<uint64_t>> dp(word1.size() + 1, vector<uint64_t>(word2.size() + 1, 0));	// dp[0][0]为0for (int i = 1; i <= word1.size(); i++) dp[i][0] = i;		// 第一列初始化为ifor (int j = 1; j <= word2.size(); j++) dp[0][j] = j;		// 第一行初始化为ifor (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], dp[i][j - 1]) + 1;}}return dp[word1.size()][word2.size()];}
};

复杂度分析：

  • 时间复杂度： O ( n ∗ m ) O(n*m) O(n∗m)， n n n和 m m m分别是两个字符串的长度。
  • 空间复杂度： O ( n ∗ m ) O(n*m) O(n∗m)。

二、72、编辑距离

在这里插入图片描述

  思路分析：本题在583题的基础之上加入了插入和替换操作。我们同样用动态规划的方法分析。

  1. 第一步，动态数组的含义。 d p [ i ] [ j ] dp[i][j] dp[i][j]代表使得 w o r d 1 [ 0 , i − 1 ] word1[0, i-1] word1[0,i−1]和 w r o d 2 [ 0 , j − 1 ] wrod2[0, j-1] wrod2[0,j−1]相等所需的最小操作数。
  2. 第二步，递推公式。 d p [ i ] [ j ] dp[i][j] dp[i][j]可以由两种情况推导出来：
  • w o r d 1 [ i − 1 ] word1[i - 1] word1[i−1]与 w o r d 2 [ j − 1 ] word2[j - 1] word2[j−1]相同：那么最小操作数和使得 w o r d 1 [ 0 , i − 2 ] word1[0, i-2] word1[0,i−2]和 w r o d 2 [ 0 , j − 2 ] wrod2[0, j-2] wrod2[0,j−2]相等所需的最小操作数相同。 d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] dp[i][j] = dp[i-1][j-1] dp[i][j]=dp[i−1][j−1]。
  • w o r d 1 [ i − 1 ] word1[i - 1] word1[i−1]与 w o r d 2 [ j − 1 ] word2[j - 1] word2[j−1]不相同：这种情况的 d p [ i ] [ j ] dp[i][j] dp[i][j]可以由三部分构成：增加、删除和替换。删除部分和583题一致： d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j ] + 1 , d p [ i ] [ j − 1 ] + 1 ) dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1) dp[i][j]=min(dp[i−1][j]+1,dp[i][j−1]+1)。而增加字符和删除的操作数没有区别。若 w o r d 1 [ 0 , i − 2 ] word1[0, i - 2] word1[0,i−2]和 w o r d 2 [ 0 , j − 2 ] word2[0, j - 2] word2[0,j−2]做了 d p [ i − 1 ] [ j − 1 ] dp[i - 1][j - 1] dp[i−1][j−1]次删除操作以后会相等，那么再替换 w o r d 1 [ i − 1 ] word1[i - 1] word1[i−1]或者 w o r d 2 [ j − 1 ] word2[j - 1] word2[j−1]之间任意一个元素以后又可以相等，即 d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 dp[i][j] = dp[i - 1][j - 1] + 1 dp[i][j]=dp[i−1][j−1]+1。因为要求最小操作数，那么我们对两项取最小： d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j ] + 1 , d p [ i ] [ j − 1 ] + 1 , d p [ i − 1 ] [ j − 1 ] + 1 ) = m i n ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j − 1 ] ) + 1 dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1) = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 dp[i][j]=min(dp[i−1][j]+1,dp[i][j−1]+1,dp[i−1][j−1]+1)=min(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])+1。
	if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];//else dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;	// min()函数只接受两个参数，或者数组else dp[i][j] = min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] }) + 1;
  1. 第三步，元素初始化。 d p [ i ] [ 0 ] dp[i][0] dp[i][0]（第一列）表示字符串 w o r d 1 [ 0 , i − 1 ] word1[0, i-1] word1[0,i−1]变成空字符串需要的最少操作数。 d p [ 0 ] [ j ] dp[0][j] dp[0][j]（第一行）表示 w o r d 2 [ 0 , j − 1 ] word2[0, j-1] word2[0,j−1]变成空字符串需要的最少操作数。其中，空字符串word1变成空字符串word2的个数为0。那么 d p [ 0 ] [ 0 ] = 0 , d p [ i ] [ 0 ] = i , d p [ 0 ] [ j ] = j dp[0][0]=0, dp[i][0] = i, dp[0][j] = j dp[0][0]=0,dp[i][0]=i,dp[0][j]=j。
	for (int i = 1; i <= word1.size(); i++) dp[i][0] = i;		// 第一列初始化为ifor (int j = 1; j <= word2.size(); j++) dp[0][j] = j;		// 第一行初始化为i
  1. 第四步，递归顺序。一共有两层循环，从前往后进行遍历。
  2. 第五步，打印结果。

在这里插入图片描述

  程序如下：

// 72、编辑距离-动态规划
class Solution2 {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));	// dp[0][0]为0for (int i = 1; i <= word1.size(); i++) dp[i][0] = i;		// 第一列初始化为ifor (int j = 1; j <= word2.size(); j++) dp[0][j] = j;		// 第一行初始化为ifor (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(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;	// min()函数只接受两个参数，或者数组else dp[i][j] = min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] }) + 1;}}return dp[word1.size()][word2.size()];}
};

复杂度分析：

  • 时间复杂度： O ( n ∗ m ) O(n*m) O(n∗m)， n n n和 m m m分别是两个字符串的长度。
  • 空间复杂度： O ( n ∗ m ) O(n*m) O(n∗m)。

三、完整代码

# include <iostream>
# include <vector>
# include <string>
using namespace std;// 583、两个字符串的删除操作-动态规划
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<uint64_t>> dp(word1.size() + 1, vector<uint64_t>(word2.size() + 1, 0));	// dp[0][0]为0for (int i = 1; i <= word1.size(); i++) dp[i][0] = i;		// 第一列初始化为ifor (int j = 1; j <= word2.size(); j++) dp[0][j] = j;		// 第一行初始化为ifor (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], dp[i][j - 1]) + 1;}}return dp[word1.size()][word2.size()];}
};// 72、编辑距离-动态规划
class Solution2 {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));	// dp[0][0]为0for (int i = 1; i <= word1.size(); i++) dp[i][0] = i;		// 第一列初始化为ifor (int j = 1; j <= word2.size(); j++) dp[0][j] = j;		// 第一行初始化为ifor (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(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;	// min()函数只接受两个参数，或者数组else dp[i][j] = min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] }) + 1;}}return dp[word1.size()][word2.size()];}
};int main() {//string word1 = "sea", word2 = "eat";	// 测试案例//Solution s1;//int result = s1.minDistance(word1, word2);string word1 = "horse", word2 = "ros";	// 测试案例Solution2 s1;int result = s1.minDistance(word1, word2);cout << result << endl;system("pause");return 0;
}

end

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

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

相关文章

Python—数据可视化Seaborn大全：参数详解与实战案例全解析【第52篇—python：Seaborn大全】

Python—数据可视化Seaborn大全：参数详解与实战案例全解析【第52篇—python：Seaborn大全】

文章目录 Seaborn库常用绘图详解与实战引言安装与导入一、散点图参数说明实战案例 二、直方图参数说明实战案例 三、线性关系图参数说明实战案例 四、热力图参数说明实战案例 五、分布图参数说明实战案例 六、箱线图参数说明实战案例 七、联合分布图参数说明实战案例 八、小提琴…
阅读更多...
echarts条形图添加滚动条

echarts条形图添加滚动条

效果展示: 测试数据: taskList:[{majorDeptName:测试,finishCount:54,notFinishCount:21}, {majorDeptName:测试,finishCount:54,notFinishCount:21}, {majorDeptName:测试,finishCount:54,notFinishCount:21}, {majorDeptName:测试,finishCount:54,notFinishCount:21}, {maj…
阅读更多...
Pytest框架测试

Pytest框架测试

Pytest 是什么？ pytest 能够支持简单的单元测试和复杂的功能测试；pytest 可以结合 Requests 实现接口测试； 结合 Selenium、Appium 实现自动化功能测试；使用 pytest 结合 Allure 集成到 Jenkins 中可以实现持续集成。pytest 支持 315 种以上的插件；为什么要选择 Pytest 丰…
阅读更多...
【axios报错异常】： Uncaught ReferenceError: axios is not defined

【axios报错异常】： Uncaught ReferenceError: axios is not defined

问题描述: 当前代码在vivo手机和小米手机运行是正常的,点击分享按钮调出相关弹框,发送接口进行分享,但是现在oppo手机出现了问题: 点击分享按钮没有反应. 问题解析: 安卓同事经过查询后,发现打印了错误: 但是不清楚这个问题是安卓端造成的还是前端造成的,大家都不清楚. 问题…
阅读更多...
图论练习3

图论练习3

内容&#xff1a;过程中视条件改变边权&#xff0c;利用树状数组区间加处理 卯酉东海道 题目链接 题目大意 个点&#xff0c;条有向边&#xff0c;每条边有颜色和费用总共有种颜色若当前颜色与要走的边颜色相同&#xff0c;则花费为若当前颜色与要走的边颜色不同&#xff0c;…
阅读更多...
Java面试——计网篇

Java面试——计网篇

一、基础篇 1、 TCP/IP 网络模型 对于同一台设备上的进程间通信&#xff0c;有很多种方式&#xff0c;比如有管道、消息队列、共享内存、信号等方式&#xff0c;而对于不同设备上的进程间通信&#xff0c;就需要网络通信&#xff0c;而设备是多样性的&#xff0c;所以要兼容多…
阅读更多...
【Java程序设计】【C00245】基于Springboot的家政服务管理平台（有论文）

【Java程序设计】【C00245】基于Springboot的家政服务管理平台（有论文）

基于Springboot的家政服务管理平台&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的家政服务管理平台 本系统分为前台模块、管理员功能模块、用户功能模块以及服务人员功能模块。 前台模块&#xff1a;系统首页的…
阅读更多...
C2-Search-Netlas：一款基于Netlas API的强大C2服务器识别与检测工具

C2-Search-Netlas：一款基于Netlas API的强大C2服务器识别与检测工具

关于C2-Search-Netlas C2-Search-Netlas是一款功能强大的命令与控制&#xff08;C2&#xff09;服务器检测工具&#xff0c;该工具使用Java语言开发&#xff0c;基于Netlas API实现其功能&#xff0c;可以帮助广大研究人员轻松快速地识别和检测目标C2服务器的相关信息。 C2-S…
阅读更多...
【目标跟踪】相机运动补偿

【目标跟踪】相机运动补偿

文章目录 一、前言二、简介三、改进思路3.1、状态定义3.2、相机运动补偿3.3、iou和ReID融合3.4、改进总结 四、相机运动补偿 一、前言 目前 MOT (Multiple Object Tracking) 最有效的方法仍然是 Tracking-by-detection。今天给大家分享一篇论文 BoT-SORT。论文地址 &#xff0…
阅读更多...
XCTF：warmup[WriteUP]

XCTF：warmup[WriteUP]

CtrlU查看页面源码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><meta http-equiv"X-UA-Compatible&q…
阅读更多...
【Matplotlib】figure方法之图形的保存

【Matplotlib】figure方法之图形的保存

&#x1f388;个人主页&#xff1a;甜美的江 &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;matplotlib &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进…
阅读更多...
idea常用设置

idea常用设置

1、内存优化 根据自己电脑本身的内存&#xff0c;对idea安装包里bin目录下的idea64.exe.vmoptions文件进行修改 -server -Xms256m -Xmx2048m -XX:MaxPermSize1024m -XX:ReservedCodeCacheSize256m -ea -Dsun.io.useCanonCachesfalse -Djava.Net.preferIPv4Stacktrue -Djsse.e…
阅读更多...
STM32--HAL库定时器学习记录（易懂）--持续学习

STM32--HAL库定时器学习记录（易懂）--持续学习

一、什么是定时器 定时器就是计数器&#xff0c;通过计数完成一系列功能。 二、定时器的分类 定时器分为基本定时器、通用定时器、高级定时器。级别不同&#xff0c;功能不同。级别越高&#xff0c;功能越强。 三、定时器&#xff08;计数器&#xff09;三个重要寄存器 预分…
阅读更多...
CSS：水平垂直居中

CSS：水平垂直居中

公共的 CSS 样式&#xff1a; .parent {width: 300px;height: 300px;background-color:#d0e4fe; }.child {width: 100px;height: 100px;background-color:orange; }HTML: <div class"parent"><div class"child"></div> </div>最…
阅读更多...
C#之linq和lamda表达式GroupBy分组拼接字符串

C#之linq和lamda表达式GroupBy分组拼接字符串

文章目录 C#之linq和lamda表达式GroupBy分组拼接字符串业务需求核心代码调试 C#之linq和lamda表达式GroupBy分组拼接字符串 业务需求 点击提示信息&#xff0c;如&#xff1a;“售后单【SH001】序列号【001&#xff0c;002&#xff0c;006】&#xff1b;售后单【SH002】序列号…
阅读更多...
华为自动驾驶干不过特斯拉？

华为自动驾驶干不过特斯拉？

文 | AUTO芯球 作者 | 李诞 什么&#xff1f; 华为的智能驾驶方案干不过蔚小理&#xff1f; 特斯拉的智能驾驶[FSD]要甩中国车企几条街&#xff1f; 这华为问界阿维塔刚刚推送“全国都能开”的城区“无图 NCA” 就有黑子来喷了 这是跪久了站不起来了吧 作为玩车14年&…
阅读更多...
flask_django_python五金电商网络营销的可视化分析研究

flask_django_python五金电商网络营销的可视化分析研究

前面部分完成了系统需求分析&#xff0c;了解到新闻数据业务方面的需求&#xff0c;系统主要分为用户管理、五金信息管理、在线留言、系统管理等功能。销的可视化研究&#xff0c;并对这些数据进行处理&#xff0c; 然后对这些数据进行可视化分析和统计。 Python 爬虫技术目前来…
阅读更多...
【华为】GRE VPN 实验配置

【华为】GRE VPN 实验配置

【华为】GRE VPN 实验配置 前言报文格式 实验需求配置思路配置拓扑GRE配置步骤R1基础配置GRE 配置 ISP_R2基础配置 R3基础配置GRE 配置 PCPC1PC2 抓包检查OSPF建立GRE隧道建立 配置文档 前言 VPN &#xff1a;&#xff08;Virtual Private Network&#xff09;&#xff0c;即“…
阅读更多...
Electron实战(二)：将Node.js和UI能力（app/BrowserWindow/dialog)等注入html

Electron实战(二)：将Node.js和UI能力（app/BrowserWindow/dialog)等注入html

文章目录 设置webPreferences参数安装electron/remotemain进程中初始化html中使用dialog踩坑参考文档 上一篇&#xff1a;Electron实战(一)&#xff1a;环境搭建/Hello World/打包exe 设置webPreferences参数 为了能够在html/js中访问Node.js提供fs等模块&#xff0c;需要在n…
阅读更多...
Django的web框架Django Rest_Framework精讲（二）

Django的web框架Django Rest_Framework精讲（二）

文章目录 1.自定义校验功能&#xff08;1&#xff09;validators&#xff08;2&#xff09;局部钩子&#xff1a;单字段校验&#xff08;3&#xff09;全局钩子&#xff1a;多字段校验 2.raise_exception 参数3.context参数4.反序列化校验后保存&#xff0c;新增和更新数据&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023