河南住房和城乡建设厅网站资质,用html做企业门户网站,兰州网络推广方法,信誉好的龙岗网站建设1143. 最长公共子序列 - 力扣#xff08;LeetCode#xff09;
给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 #xff0c;返回 0 。
一个字符串的 子序列 是指这样一个新的字符串#xff1a;它是由原字符串…1143. 最长公共子序列 - 力扣LeetCode
给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。
一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。
例如ace 是 abcde 的子序列但 aec 不是 abcde 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1
输入text1 abcde, text2 ace
输出3
解释最长公共子序列是 ace 它的长度为 3 。示例 2
输入text1 abc, text2 abc
输出3
解释最长公共子序列是 abc 它的长度为 3 。示例 3
输入text1 abc, text2 def
输出0
解释两个字符串没有公共子序列返回 0 。 思路和分析
本题和 leetCode 718.最长重复子数组 区别在于这里不要求是连续的了但是要有相对顺序即ace 是 abcde 的子序列 但是 aec 不是 abcde 的子序列
动规五部曲
1.确定dp数组dp table以及下标的含义
dp[i][j] : 长度为 [0,i-1] 的字符串 text1 与长度为 [0,j-1]的字符串text2的最长公共子序列为dp[i][j]
2.确定递推公式 思考有哪些方向可以推出dp[i][j]
text1[i-1] text[j-1]时dp[i][j]dp[i-1][j-1]1text1[i-1] ! text[j-1]时分两种情况讨论 情况①: 不看e了考虑c就是abc和ac。这两个原字符串的最长公共子序列也可能是abc和ac的最长公共子序列。因为c和e明显不相同那么可不考虑e了情况②: 同理也可以不看c了考虑e就是ab和ace。这两个字符串也可能是两个原字符串的最长公共子序列那么这两种情况应该怎么取呢这两种情况都有可能是dp[i][j]那么 dp[i][j] max(dp[i][j-1],dp[i-1][j]); 情况①对应dp[i][j-1]情况②对应dp[i-1][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]);
3.dp数组初始化
dp[i][0] 应该初始化为0因为 test1[0,i-1] 和空串的最长公共子序列是0dp[0][j] 同理也为0其他下标都是随着递推公式逐步覆盖初始为多少都可以
故统一初始为0代码如下
vectorvectorint dp(text1.size() 1, vectorint(text2.size() 1, 0));4.确定遍历顺序 那么为了在递推的过程中这三个方向都是经过计算的数值所以要从前向后从上到下来遍历这个矩阵
5.举例推导dp数组 由上图可看到dp[text1.size()][text2.size()]为最终结果
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vectorvectorint dp(text1.size() 1, vectorint(text2.size() 1, 0));for (int i 1; i text1.size(); i) {for (int j 1; j text2.size(); 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[text1.size()][text2.size()];}
};
时间复杂度: O(n * m)其中 n 和 m 分别为 text1 和 text2 的长度空间复杂度: O(n * m)
优化空间复杂度
class Solution {
public:// 滚动数组int longestCommonSubsequence(string text1, string text2) {vectorint dp(text2.size() 1, 0);for(int i1;itext1.size();i) {int pre dp[0];for(int j1;jtext2.size();j) {int tmp dp[j];if(text1[i-1] text2[j-1]) dp[j] pre 1;else dp[j] max(dp[j-1],dp[j]);pre tmp;}}return dp[text2.size()];}
};
时间复杂度: O(n * m)其中 n 和 m 分别为 text1 和 text2 的长度空间复杂度: O(m)
参考文章和视频
动态规划子序列问题经典题目 | LeetCode1143.最长公共子序列_哔哩哔哩_bilibili 代码随想录 (programmercarl.com)
来自代码随想录课堂截图
