题目
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 。
提示:
1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。
思路
-
设dp[i][j]
表示[0,i-1]
的text1字符串和[0,j-1]
的text2字符串的最长公共子序列的长度
-
递推关系,if(text1[i - 1] === text2[j - 1]) { dp[i][j] = dp[i-1][j-1] + 1}
如果不相等,那就选则dp[i-1][j]
和dp[i][j-1]
中较大的
-
dp数组初始化为0即可
-
由递推关系知,当前dp[i][j]
依赖于左边、上边和左上斜对角元素的值,因此要从上到下,从左往右遍历
-
返回dp[len1][len2]
即可
代码
/**
* @param {string} text1
* @param {string} text2
* @return {number}
*/
var longestCommonSubsequence = function(text1, text2) {
let len1 = text1.length , len2 = text2.length
let dp = (new Array(len1 + 1)).fill(0).map(x => new Array(len2 + 1).fill(0))
for(let i = 1 ; i <= len1 ; i++){
for(let 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] = Math.max(dp[i-1][j] , dp[i][j-1])
}
}
return dp[len1][len2]
};
复杂度
- 时间复杂度:
O
(
n
∗
m
)
O(n*m)
O(n∗m)
- 空间复杂度:
O
(
n
∗
m
)
O(n*m)
O(n∗m)
- n 、m分别表示text1和text2的长度
关注我的专栏,每天更新三道leetcode题解,一起变强!