动态规划
解题思路
确定 dp 数组以及下标的含义：长度为 [0, i - 1] 的字符串 text1 与长度为 [0, j - 1] 的字符串 text2 的最长公共子序列为 dp[i][j]；
- 也可以定义成：长度为 [0, i] 的字符串 text1 与长度为 [0, j] 的字符串 text2 的最长公共子序列为 dp[i][j]；
- 在 leetcode🧑💻 718. 最长重复子数组 有过解释，可以去详细看下；
确定递推公式：
- 如果 text1[i - 1] 与 text2[j - 1] 相同，那么找到了一个公共元素，所以 dp[i][j] = dp[i - 1][j - 1] + 1；
- 如果 text1[i - 1] 与 text2[j - 1] 不相同，那就看看 text1[0, i - 2] 与 text2[0, j - 1] 的最长公共子序列和 text1[0, i - 1] 与 text2[0, j - 2] 的最长公共子序列，取最大的，即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])；
如何初始化 dp 数组：
- test1[0, i - 1] 和空串的最长公共子序列自然是 0，所以 dp[i][0] = 0；
- 同理 dp[0][j] 也是 0；
确定遍历顺序：由递推公式可知，要从前向后，从上到下来遍历这个矩阵；
举例推导 dp 数组：以 text1 = “abcde”，text2 = “ace” 为例：
j = 0 j = 1 j = 2 j = 3 dp[0][j] 0 0 0 0 dp[1][j] 0 1 1 1 dp[2][j] 0 1 1 1 dp[3][j] 0 1 2 2 dp[4][j] 0 1 2 2 dp[5][j] 0 1 2 3
复杂度
-
时间复杂度:
O(n * m)，其中 n 和 m 分别为 text1 和 text2 的长度； -
空间复杂度:
O(n * m)；
代码实现
var longestCommonSubsequence = function (text1, text2) {
const m = text1.length;
const n = text2.length;
let dp = new Array(m + 1).fill(0).map(i => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; 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[m][n];
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 718. 最长重复子数组
上一篇
评论
