当前位置:   article > 正文

【leetcode-1143】最长公共子序列_leetcode最长公共子串

leetcode最长公共子串

题目链接

1143. 最长公共子序列

题目描述

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

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 1 <= text1.length <= 1000
  • 1 <= text2.length <= 1000
  • 输入的字符串只含有小写英文字符。

解题思路

详细题解参考 动态规划之最长公共子序列(LCS)

这是一道非常经典的面试题,因为它采用的解法是典型的二维动态规划。

对于子序列问题,穷举出所有可能的结果都不容易,而动态规划算法要做的就是穷举+剪枝,所以说只要涉及子序列的问题,十有八九都是用动态规划来解决。

而对于两个字符串的动态规划问题,套路是通用的,就是需要一个二维数组。

动态规划三步走

定义dp数组

注意这里由于有两个字符串,所以我们需要定义一个二维的dp数组。

dp[i][j] 表示对于 s1[1…i] 和 s2[1…j],它们的最长公共子序列(LCS)长度是 dp[i][j]
确定 base case

根据dp数组的定义。我们就可以确定 base case,即

dp[i][0], dp[0][j] = 0

因为只要有一个字符串是空串,它们的最长公共子序列的长度显然应该是 0。

推导状态转移方程

依旧是采用数学归纳法来寻找状态转移关系:假设我们已经计算出了dp[i-1][j-1],dp[i-1][j]以及dp[i][j-1],如何推导出dp[i][j]呢?

dp[i][j]其实只有两种选择,要么就是与前面的子序列连接,形成一个更长的公共子序列,要么不与前面的子序列连接,原来的最长子序列保持不变。而做出这个选择的关键就在于s[i]是否等于s[j]

             dp[i-1][j-1] + 1,            当s[i]==s[j]时
dp[i][j] = 
             max(dp[i][j-1], dp[i-1][j]), 当s[i]!=s[j]时
  • 1
  • 2
  • 3
至此,我们列出状态转移方程,就可以直接写代码了。

题解

func longestCommonSubsequence(text1 string, text2 string) int {
	// 定义 dp 数组
	l1, l2 := len(text1), len(text2)
	// 这里是一个二维数组, 注意二维数组的长度是字符串长度+1
	dp := make([][]int, l1+1)
	for k := range dp {
		dp[k] = make([]int, l2+1)
	}
	// 开始遍历,注意下标从1开始
	for i := 1; i <= l1 ; i++ {
		for j := 1; j <= l2 ; j++ {
			// 如果s[i]等于s[j],说明此时s[i]和s[j]属于公共子序列,公共子序列+1
			if text1[i-1] == text2[j-1] {
				dp[i][j] = dp[i-1][j-1] +1
			} else {
				// 如果s[i]不等于s[j],说明s[i]和s[j]至少有一个不属于公共子序列,子序列长度不变
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	return dp[l1][l2]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

复杂度分析

时间复杂度:O(n^2)

需要两层循环遍历两个字符串。

空间复杂度:O(n^2)

需要定义一个二维的dp数组。

反思

最长公共子序列是一道非常经典的面试题目,因为它的解法是典型的二维动态规划,大部分比较困难的字符串问题都和这个问题一个套路,比如说编辑距离。而且,这个算法稍加改造就可以用于解决其他问题,所以说 LCS 算法是值得掌握的。

所谓二维无非就是比一维多了一维,我们只需要在定义dp数组,base case以及推导状态转移方程上多一个维度的思考就行了

需要尤其注意的是二维数组开辟的大小比两个字符串的大小要+1。这是因为需要专门让索引为 0 的行和列表示空串,dp[0][…] 和 dp[…][0] 都应该初始化为 0,相当于 base case。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/169421
推荐阅读
相关标签
  

闽ICP备14008679号