标签搜索

目 录CONTENT

文章目录

最⻓公共⼦序列.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 13 阅读 / 3,525 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

最⻓公共⼦序列

@[toc]

一、问题描述

给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列。

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

例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。
两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列,则返回 0。

示例 1:

输入:text1 = "abcde", text2 = "ace" 
输出:3  
解释:最长公共子序列是 "ace",它的长度为 3。

示例 2:

输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 "abc",它的长度为 3。

示例 3:

输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有公共子序列,返回 0。

提示:

  • 1 <= text1.length <= 1000
  • 1 <= text2.length <= 1000

输入的字符串只含有小写英文字符。

⼀、 动态规划思路

第⼀步, ⼀定要明确 dp 数组的含义。 对于两个字符串的动态规划问题,套路是通⽤的

⽐如说对于字符串 s1 和 s2 , ⼀般来说都要构造⼀个这样的 DP table:
在这里插入图片描述

为了⽅便理解此表, 我们暂时认为索引是从 1 开始的, 待会的代码中只要稍作调整即可。

其中, dp[i][j] 的含义是: 对于 s1[1..i] 和 s2[1..j] ,它们的 最长公共子序列 ⻓度是 dp[i][j] 。

⽐如上图的例⼦, d[2][4] 的含义就是: 对于 "ac" 和 "babc" , 它们的最长公共子序列 ⻓度是 2。 我们最终想得到的答案应该是 dp[3][6] 。

第⼆步, 定义 base case

我们专门让索引为 0 的⾏和列表⽰空串, dp[0][..] 和 dp[..][0] 都应该初始化为 0, 这就是 base case。

⽐如说, 按照刚才 dp 数组的定义, dp[0][3]=0 的含义是: 对于字符串"" 和 "bab" , 其最长公共子序列的⻓度为 0。 因为有⼀个字符串是空串, 它们的最⻓公共⼦序列的⻓度显然应该是 0

第三步, 找状态转移⽅程

这是动态规划最难的⼀步, 不过好在这种字符串问题的套路都差不多, 权且借这道题来聊聊处理这类问题的思路

状态转移说简单些就是做选择, ⽐如说这个问题, 是求 s1 和 s2 的最⻓公共⼦序列, 不妨称这个⼦序列为 lcs 。 那么对于 s1 和 s2 中的每个字符, 有什么选择?

很简单, 两种选择, 要么在 lcs 中, 要么不在
在这里插入图片描述

这个「」 和「不在」 就是选择, 关键是, 应该如何选择呢?

这个需要动点脑筋: 如果某个字符应该在 lcs 中, 那么这个字符肯定同时存在于 s1 和s2 中, 因为 lcs 是最⻓公共⼦序列嘛

所以本题的思路是这样:

⽤两个指针 i 和 j 从后往前遍历 s1 和 s2 , 如果 s1[i]==s2[j] , 那么这个字符⼀定在 lcs 中; 否则的话, s1[i] 和 s2[j] 这两个字符⾄少有⼀个不在 lcs 中, 需要丢弃⼀个。 先看⼀下递归解法, ⽐较容易理解:

def longestCommonSubsequence(str1, str2) -> int:
	def dp(i, j):
	# 空串的 base case
		if i == -1 or j == -1:
			return 0
		if str1[i] == str2[j]:
			# 这边找到⼀个 lcs 的元素, 继续往前找
			return dp(i - 1, j - 1) + 1
		else:
			# 谁能让 lcs 最⻓, 就听谁的
			return max(dp(i-1, j), dp(i, j-1))
		# i 和 j 初始化为最后⼀个索引
return dp(len(str1)-1, len(str2)-1)

对于第⼀种情况, 找到⼀个 lcs 中的字符, 同时将 i j 向前移动⼀位, 并给 lcs 的⻓度加⼀; 对于后者, 则尝试两种情况, 取更⼤的结果

方法一:动态规划(直接加上备忘录,否则会超时)

class Solution {
public:
    int dp(string& s1, string& s2,int i,int j,vector<vector<int>>& ret)
    {
        //当有 i 或者 j 任意一个小于0,就代表其遍历结束 或者 它本身就是空字符串,但是结果都是返回0,因为已经没有字符了嗨皮配个求,直接return0;
        if(i < 0 || j < 0)
        {
            return 0;
        }

        //优先在备忘录中查找,避免重复当计算
        if(ret[i][j] != -1)
        {
            return ret[i][j];
        }

        //如果当前位置当两个字符相等,最长公共子序列当长度加一,继续往前递归
        if(s1[i] == s2[j])
        {
            ret[i][j] = dp(s1,s2,i - 1,j - 1,ret) + 1;
        }
        else//如果当前两个位置不想等,注意:1.i位置当字符可能出现
        //在最长公共子序列中;2.j位置当字符可能出现在最长公共子序列当中;
        //3.i和j两个字符都不出现在公共子序列当中,主要的情况是1,2两种,
        //递归选取其中能让最长公共子序列的长度最大的一个结果,对于第3种情
        //况,是可以不加在代码中和其他两种进行比较的,因为第3种情况的最长公
        //共子序列肯定比第1,2两种情况短的,在进行max时肯定取不到它的值,
        //所以直接省道。注意此处的长度不要加一,因为只有响应的字符相等时才可以加一
        {
            ret[i][j] = max(dp(s1,s2,i - 1,j,ret),dp(s1,s2,i,j - 1,ret));
        }

        return ret[i][j];

    }
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> ret(text1.size() + 1,vector<int>(text2.size() + 1,-1));
        return dp(text1,text2,text1.size() - 1,text2.size() - 1,ret);
    }
};

方法二:DP table解法

def longestCommonSubsequence(str1, str2) -> int:
	m, n = len(str1), len(str2)
	# 构建 DP table 和 base case
	dp = [[0] * (n + 1) for _ in range(m + 1)]
	# 进⾏状态转移
	for i in range(1, m + 1):
		for j in range(1, n + 1):
			if str1[i - 1] == str2[j - 1]:
				# 找到⼀个 lcs 中的字符
				dp[i][j] = 1 + dp[i-1][j-1]
			else:
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]

C++代码:

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        //注意此处初始化就不能初始化为 -1 了,得初始化为0,避免影响结果
        vector<vector<int>> dp(text1.size() + 1,vector<int>(text2.size() + 1,0));

        //遍历
        for(int i = 1;i < text1.size() + 1;i++)
        {
            for(int j = 1;j < text2.size() + 1;j++)
            {
                //注意i和j只从1开始的
                //如果当前两个字符相等,就把dp[i - 1][j - 1]的结果 + 1赋值给dp[i][j](相当于把i - 1,j - 1之前的最长公共梓序列的长度 加上此时相等一个字符就等于i和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]);
                }
            }
        }
        //返回结果,注意vector的大小定义
        return dp[text1.size()][text2.size()];
    }
};

三、 总结

对于两个字符串的动态规划问题, ⼀般来说都是像本⽂⼀样定义 DP table,因为这样定义有⼀个好处, 就是容易写出状态转移⽅程, dp[i][j] 的状态可以通过之前的状态推导出来:
在这里插入图片描述

0

评论区