面试算法题精讲：最长公共子序列

面试算法题精讲：最长公共子序列

题面

题目来源：1143. 最长公共子序列

题目描述：

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列（LCS）的长度。如果不存在公共子序列 ，返回 0 。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。

两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

解法1：记忆化搜索

代码：

// 记忆化搜索

class Solution
{
public:
    int longestCommonSubsequence(string s, string t)
    {
        int n = s.length(), m = t.length();
        int memo[n][m];
        memset(memo, -1, sizeof(memo)); // -1 表示没有访问过
        function<int(int, int)> dfs = [&](int i, int j) -> int
        {
            if (i < 0 || j < 0)
                return 0;
            int &res = memo[i][j];
            if (res != -1)
                return res;
            if (s[i] == t[j])
                return res = dfs(i - 1, j - 1) + 1;
            return res = max(dfs(i - 1, j), dfs(i, j - 1));
        };
        return dfs(n - 1, m - 1);
    }
};

结果：

在这里插入图片描述

复杂度分析：

时间复杂度：O(nm)，其中 m 和 n 分别是字符串 s 和 t 的长度。

空间复杂度：O(nm)，其中 m 和 n 分别是字符串 s 和 t 的长度。

解法2：动态规划

代码：

// 动态规划

class Solution
{
public:
    int longestCommonSubsequence(string text1, string text2)
    {
        // 特判
        if (text1.empty() || text2.empty())
            return 0;
        int len1 = text1.size(), len2 = text2.size();
        // 状态数组，并初始化
        //  dp[i][j]表示到text1的位置i为止、到text2的位置j为止、最长的公共子序列长度
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        // 状态转移
        for (int i = 1; i <= len1; i++)
            for (int j = 1; j <= len2; j++)
            {
                if (text1[i - 1] == text2[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 dp[len1][len2];
    }
};

结果：

在这里插入图片描述

复杂度分析：

时间复杂度：O(nm)，其中 m 和 n 分别是字符串 s 和 t 的长度。

空间复杂度：O(nm)，其中 m 和 n 分别是字符串 s 和 t 的长度。

解法3：动态规划：空间优化

代码：

// 动态规划：空间优化

class Solution
{
public:
    int longestCommonSubsequence(string s, string t)
    {
        int n = s.length(), m = t.length(), dp[2][m + 1];
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
            {
                if (s[i] == t[j])
                    dp[(i + 1) % 2][j + 1] = dp[i % 2][j] + 1;
                else
                    dp[(i + 1) % 2][j + 1] = max(dp[i % 2][j + 1], dp[(i + 1) % 2][j]);
            }
        return dp[n % 2][m];
    }
};

结果：

在这里插入图片描述

复杂度分析：

时间复杂度：O(nm)，其中 m 和 n 分别是字符串 s 和 t 的长度。

空间复杂度：O(nm)，其中 m 是字符串 t 的长度。

进阶：求最长公共子序列的内容

前面我们只是通过动态规划求得了两个字符串的最长公共子序列长度。我们要怎么样根据dp得到我们想要的LCS序列字符数组呢？

原理：由于我们填表的时候，当找到一个公共字符我们就会将dp[i][j]的值设置为dp[i-1][j-1] + 1的值，那么这个值也就是我们根据dp表找公共子序列的那个字符。

图解：

在这里插入图片描述

寻找字符的过程：

  1. 从 dp[m][n] 开始回溯;
  2. 如果 dp[i][j] == dp[i-1][j-1] + 1（即dp[i][j] != dp[i-1][j] && dp[i][j] != dp[i][j-1]），说明 s[i-1] == t[j-1]，我们找到了一个公共字符，插入lcs中，i–，j–，往左上角回溯；
  3. 否则，如果 dp[i][j] == dp[i-1][j]，i–，往上回溯；如果 dp[i][j] == dp[i][j-1]，j–，往左回溯。
  4. 由于lcs是逆序插入公共字符的，我们把lcs倒序一下，lcs就是最长公共子序列字符串了。

在这里插入图片描述

在这里插入图片描述

最终情况：

在这里插入图片描述

《算法导论》中回溯输出最长公共子序列过程：

在这里插入图片描述

实现代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	string s = "ABCABCDEFG";
	string t = "ABXYZCCDEXYZ";

	int n = s.size(), m = t.size();
	// dp[i][j]表示到s的位置i为止、到t的位置j为止、最长的公共子序列长度
	vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0));
	// 状态转移
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			if (s[i - 1] == t[j - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}

	int lscLen = dp[n][m];
	cout << lscLen << endl;

	string lsc = string(lscLen, 0);
	int i = n, j = m, k = lscLen, idx = 0;
	while (k)
	{
		if (dp[i][j] == dp[i - 1][j])
			i--;
		else if (dp[i][j] == dp[i][j - 1])
			j--;
		else
		{
			lsc[idx++] = s[i - 1];
			i--;
			j--;
			k--;
		}
	}
	reverse(lsc.begin(), lsc.end());
	cout << lsc << endl;

	system("pause");
	return 0;
}

我们还可以把整个过程包装成一个函数：

string longestCommonSubsequence(string s, string t)
{
	// 特判
	if (s.empty() || t.empty())
		return 0;
	int n = s.size(), m = t.size();
	//  dp[i][j]表示到s的位置i为止、到t的位置j为止、最长的公共子序列长度
	vector<vector<int> > dp(n + 1, vector<int>(m + 1));
	// state
	vector<vector<int> > state(n + 1, vector<int>(m + 1));
	// 初始化
	for (int i = 0; i <= n; i++)
		dp[i][0] = 0;
	for (int j = 0; j <= m; j++)
		dp[0][j] = 0;
	// 状态转移
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			if (s[i - 1] == t[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
				state[i][j] = 0; // 为了后面回溯，作为公共子序列的判定
			}
			else if (dp[i - 1][j] >= dp[i][j - 1])
			{
				dp[i][j] = dp[i - 1][j];
				state[i][j] = 1; // 为了后面向上回溯，向上寻找子序列的判定
			}
			else
			{
				dp[i][j] = dp[i][j - 1];
				state[i][j] = 2; // 为了后面向左回溯，向左寻找子序列的判定
			}
		}
	int lscLen = dp[n][m];
	string lsc = string(lscLen, 0);
	int i = n, j = m, k = lscLen - 1;
	while (k >= 0)
	{
		if (state[i][j] == 0) // 找到了公共字符，往左上回溯 
		{
			lsc[k--] = s[i - 1];
			i--;
			j--;
		}
		else if (state[i][j] == 1) // 向上回溯 
			i--;
		else // 向左回溯 
			j--;
	}
	return lsc;
}

在动态规划求LCS的长度时，用state数组标记转移状态，在求LCS时参考state就能知道往哪个方向回溯了。

参考

  1. https://blog.csdn.net/weixin_54408360/article/details/126925084
  2. https://blog.csdn.net/lxt_Lucia/article/details/81209962
  3. https://blog.csdn.net/2301_77329667/article/details/136479874

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

C++ ─── 匿名对象+变量的创建顺序

C++ ─── 匿名对象+变量的创建顺序

目录 1. 匿名对象&#xff08;临时对象&#xff09; 2. 编译器的优化 3.变量的创建与销毁 1. 匿名对象&#xff08;临时对象&#xff09; 我们先来看有名对象的创建 Date d1; Date d2(2024,4,27);匿名对象的创建 Date(2024,56,1); 生成了一个匿名对象&#xff0c;执行完Da…
阅读更多...
MySQL之binlog归档日志

MySQL之binlog归档日志

binlog&#xff08;二进制归档日志&#xff09; binlog 二进制日志记录保存所有执行过的修改操作语句&#xff0c;不保存查询操作。如果 MySQL 服务意外停止&#xff0c;可通过二进制日志文件排查&#xff0c;用户操作或表结构操作&#xff0c;从而来恢复数据库数据。启动 bin…
阅读更多...
Vue的安装及使用教程【超详细图文教程】

Vue的安装及使用教程【超详细图文教程】

一、安装Node.js 安装步骤详细见Node.js下载安装及环境配置 》https://blog.csdn.net/WHF__/article/details/129362462 二、安装vue ①安装 vue.js&#xff1a; npm install vue -g // -g为全局安装 注意&#xff1a;要以管理员身份运行cmd命令窗口&#xff01;&#xf…
阅读更多...
深入浅出MySQL-02-【MySQL支持的数据类型】

深入浅出MySQL-02-【MySQL支持的数据类型】

文章目录 前言1.数值类型2.日期时间类型3.字符串类型3.1.CHAR和VARCHAR类型3.2.ENUM类型3.3.SET类型 4.JSON类型 前言 环境&#xff1a; Windows11MySQL-8.0.35 1.数值类型 MySQL中的数值类型&#xff0c;如下&#xff1a; 整数类型字节最小值最大值TINYINT1有符号 -128无…
阅读更多...
从 Apache Doris 到 SelectDB Cloud：云原生架构下的弹性能力揭秘

从 Apache Doris 到 SelectDB Cloud：云原生架构下的弹性能力揭秘

随着云时代的到来&#xff0c;越来越多企业开始在公有云、私有云乃至 K8s 容器平台构建实时数据平台。云计算基础设施的革新&#xff0c;促使着数据仓库朝着云原生的方向发展。而用户日益复杂的业务负载和降本增效的需求&#xff0c;对于系统资源的精细化管理和成本效益等方面提…
阅读更多...
64、二分-搜索二维矩阵

64、二分-搜索二维矩阵

思路&#xff1a; 通过使用二分方式&#xff0c;对于每行进行二分&#xff0c;因为每行的最后一个数小于下一行的第一个数&#xff0c;我们就可以依次二分。首先取出行数N&#xff0c;然后从0-N进行二分&#xff0c;如果mid最后一个数小于目标值说明0-mid中没有&#xff0c;舍弃…
阅读更多...
36 线程概念

36 线程概念

本章重点 1.了解线程概念&#xff0c;理解线程与进程的区别与联系 2.学会现充控制&#xff0c;线程创建&#xff0c;线程终止&#xff0c;线程等待 3.了解现场分离与线程安全 4.学会线程同步 5.学会使用互斥量&#xff0c;条件变量&#xff0c;posix信号量&#xff0c;以及读写…
阅读更多...
cnpm安装

cnpm安装

npm install -g cnpm --registryhttps://registry.npmmirror.com # 注册模块镜像 npm set registry https://registry.npmmirror.com // node-gyp 编译依赖的 node 源码镜像 npm set disturl https://npmmirror.com/dist // 清空缓存 npm cache clean --force // 安装c…
阅读更多...
Linux中的yum和gcc/g++

Linux中的yum和gcc/g++

一、快速认识yum&#xff08;简单介绍&#xff09; 在Linux中&#xff0c;我们也要进行工具/指令/程序、安装、检查、卸载等等&#xff0c;需要使用到yum 在Linux中安装软件的方式&#xff1a; 源代码安装——交叉编译的工作rpm包直接安装yum/apt-get yum:yum是我们Linux预…
阅读更多...
Androd SharedPreferences 存取key-value键值对的用法小结

Androd SharedPreferences 存取key-value键值对的用法小结

文章目录 一、存储数据二、读取数据三、删除数据3.1 删除指定KEY的数据3.2 删除所有数据 四、测试4.1 查找数据文件4.2 查看数据的存储 在开发一个简单Launcher&#xff0c;点击APP按钮后&#xff0c;如无APP绑定&#xff0c;则弹出一个APP选择列表&#xff0c;选择后进行绑定&…
阅读更多...
STL--string详解

STL--string详解

STL基本内容 string是什么 string实质上是一个对象 string可看作一个串&#xff0c;类似字符数组 可以扩容&#xff0c;可以增删查改 可用下表访问操作符[]引用&#xff0c;修改某值 构造函数 默认构造 拷贝构造&#xff1a;参数为(string 或 char*) 求string对象的长度不…
阅读更多...
AI预测体彩排列3第2套算法实战化测试第5弹2024年4月27日第5次测试

AI预测体彩排列3第2套算法实战化测试第5弹2024年4月27日第5次测试

今天继续进行新算法的测试&#xff0c;今天是第5次测试。好了&#xff0c;废话不多说了&#xff0c;直接上图上结果。 2024年4月27日体彩排3预测结果 6码定位方案如下&#xff1a; 百位&#xff1a;6、2、1、7、8、9 十位&#xff1a;8、9、4、3、1、0 个位&#xff1a;3、7、8…
阅读更多...
【C++】学习笔记——类和对象5

【C++】学习笔记——类和对象5

文章目录 二、类和对象14. 日期类的实现15. const成员16. 取地址重载17. 再谈构造函数初始化列表 18. explicit关键字19. static成员 未完待续 二、类和对象 14. 日期类的实现 上一篇我们已经大致将日期类的重要功能都给实现了&#xff0c;这节将会对日期类进行完善&#xff…
阅读更多...
在Windows10上安全弹出U盘的三种方法，总有一种适合你

在Windows10上安全弹出U盘的三种方法，总有一种适合你

序言 为了避免数据丢失&#xff0c;你有必要学习如何在使用完外部硬盘或U盘后安全地将其从计算机中取出。如果在断开U盘之前不弹出&#xff0c;你可能会面临数据损坏的问题。所以不要懒惰。那么&#xff0c;如何从计算机中弹出外部硬盘驱动器或U盘&#xff1f;看看这里。这篇文…
阅读更多...
强化训练：day5（游游的you、腐烂的苹果、孩子们的游戏(圆圈中最后剩下的数)

强化训练：day5（游游的you、腐烂的苹果、孩子们的游戏(圆圈中最后剩下的数)

文章目录 前言1. 游游的you1.1 题目描述1.2 解题思路1.3 代码实现 2. 腐烂的苹果2.1 题目描述2.2 解题思路2.3 代码实现 3. 孩子们的游戏(圆圈中最后剩下的数)3.1 题目描述3.2 解题思路3.3 代码实现 总结 前言 本章内容&#xff1a;游游的you、腐烂的苹果、孩子们的游戏(圆圈中…
阅读更多...
【03】JAVASE-分支语句【从零开始学JAVA】

【03】JAVASE-分支语句【从零开始学JAVA】

Java零基础系列课程-JavaSE基础篇 Lecture&#xff1a;波哥 Java 是第一大编程语言和开发平台。它有助于企业降低成本、缩短开发周期、推动创新以及改善应用服务。如今全球有数百万开发人员运行着超过 51 亿个 Java 虚拟机&#xff0c;Java 仍是企业和开发人员的首选开发平台。…
阅读更多...
Redis 服务等过期策略和内存淘汰策略解析

Redis 服务等过期策略和内存淘汰策略解析

redis服务是基于内存运行的&#xff0c;所以很多数据都存放在内存中&#xff0c;但是内存又不是无限的&#xff0c;所以redis就引出了key的过期和淘汰策略。 一、Redis的过期策略&#xff1a; 我们在set key的时候&#xff0c;可以给它设置一个过期时间&#xff0c;比如expire …
阅读更多...
Autosar MCAL-RH850P1HC Fls配置

Autosar MCAL-RH850P1HC Fls配置

文章目录 FlsFlsGeneralFlsAcLoadOnJobStartFlsBaseAddressFlsBlankCheckApiFlsCancelApiFlsCompareApiFlsCopySupportedFlsCriticalSectionProtectionFlsDevErrorDetectFlsDeviceNameFlsDriverIndexFlsFaciEccCheckFlsGetJobResultApiFlsGetStatusApiFlsLoopCountFlsReadImmed…
阅读更多...
（待更）DRF： 序列化器、View、APIView、GenericAPIView、Mixin、ViewSet、ModelViewSet的源码解析

（待更）DRF： 序列化器、View、APIView、GenericAPIView、Mixin、ViewSet、ModelViewSet的源码解析

前言&#xff1a;还没有整理&#xff0c;后续有时间再整理&#xff0c;目前只是个人思路&#xff0c;文章较乱。 注意路径匹配的“/” 我们的url里面加了“/”&#xff0c;但是用apifox等非浏览器的工具发起请求时没有加“/”&#xff0c;而且还不是get请求&#xff0c;那么这…
阅读更多...
大语言模型在研究领域的应用——信息检索中的大语言模型

大语言模型在研究领域的应用——信息检索中的大语言模型

信息检索中的大语言模型 大语言模型提升信息检索任务利用大语言模型进行信息检索大语言模型增强的信息检索模型. 检索增强的大语言模型输入优化策略.指令微调策略.预训练策略. 总结应用建议未来方向 大语言模型对于传统信息检索技术与应用范式带来了重要影响。这两者在技术路径…
阅读更多...
最新文章

Copyright @ 2022~2023