最长公共子序列
解题思路：
-
状态表示： 定义 dp[i][j] 表示字符串 text1 的 [1,i] 区间和字符串 text2 的 [1,j] 区间的最长公共子序列长度（下标从1开始）；
-
状态计算：可以根据 text1[i] 和 text2[j] 的情况，分为两种决策：
- 若 text1[i] == text2[j]，即两个字符串的最后一位相等，那么就转化成了字符串 text1的[1,j-1] 区间和字符串 text2的[1,j-1] 区间的最长公共子序列长度再加上一，即 dp[i][j] = dp[i - 1][j - 1] + 1，（下标从1开始）；
![]( "最长公共子序列")
- 若 text1[i] != text2[j]，即两个字符串的最后一位不相等，那么字符串 text1的[1,i] 区间和字符串 text2的[1,j] 区间的最长公共子序列长度无法延长，因此 dp[i][j] 就会继承 dp[i-1][j] 与 dp[i][j-1] 中的较大值，即 dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]) ，（ 下标从1开始）；如图所示：比较 text1[3] 与 text2[3]，发现’f’不等于’e’，这样 dp[3][3] 无法在原先的基础上延长；因此继承"ac"与"cfe"，"acf"与"cf"的最长公共子序列中的较大值；即 dp[3][3] = max(dp[2][3] ,dp[3][2]) = 2；
![]( "最长公共子序列")
- 若 text1[i] == text2[j]，即两个字符串的最后一位相等，那么就转化成了字符串 text1的[1,j-1] 区间和字符串 text2的[1,j-1] 区间的最长公共子序列长度再加上一，即 dp[i][j] = dp[i - 1][j - 1] + 1，（下标从1开始）；
-
状态转移方程为：
- 当text1[i] == text2[j]：dp[i][j] = dp[i-1][j-1] + 1；
- 当text1[i] != text2[j]：dp[i][j] = max(dp[i - 1][j],dp[i][j - 1])；
-
初始化：
- dp[i][0] = dp[0][j] = 0；
- 空字符串与有长度的字符串的最长公共子序列长度肯定为 0；
-
实现细节：
- 前面定义的状态表示 dp 数组和 text 数组下标均是从 1 开始的，而题目给出的 text 数组下标是从 0 开始的；
- 为了一一对应，在判断 text1 和 text2 数组的最后一位是否相等时，往前错一位，即使用text1[i - 1]和 text2[j - 1] 来判断；
复杂度：
-
时间复杂度：O(mn)，其中 m 和 n 分别是字符串 text1 和 text2 的长度，二维数组 dp 有 m+1 行和 n＋1 列，需要对 dp 中的每个元素进行计算；
-
空间复杂度：O(mn)，其中 m 和 n 分别是字符串 text1 和 text2 的长度，创建了 m+1 行 n+1 列的二维数组 dp；
代码实现：
var longestCommonSubsequence = function (text1, text2) {
let dp = new Array(text1.length + 1).fill(0).map(i => new Array(text2.length + 1).fill(0))
for (let i = 1; i <= text1.length; i++) {
for (let j = 1; j <= text2.length; 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[text1.length][text2.length]
};
扫码领红包
您的打赏是我前进的动力
微信
支付宝
392.判断子序列
上一篇
评论
