LeetCode 题解：1143. 最长公共子序列，动态规划，JavaScript，详细注释

Lee Chen

关注

发布于: 2021 年 02 月 19 日

LeetCode题解：1143. 最长公共子序列，动态规划，JavaScript，详细注释

原题链接：https://leetcode-cn.com/problems/longest-common-subsequence/

解题思路：

我们来看这样一个 Case：text1 = "xabccde", text2 = "ace"，将两个字符串分别作为表格行列排列如下图：

图片来自：[C++ with picture, O(nm)](https://leetcode.com/problems/longest-common-subsequence/discuss/348884/C%2B%2B-with-picture-O(nm))。

假设text1长度为m，索引为i。text2长度为n，索引为j。
公共子序列要判断每个字母是否相等，dp[i][j]的状态必须由dp[i - 1][j - 1]推导而来，因此我们可以创建一个(m + 1) * (n + 1)的矩阵。将索引0的位置，即空字符串作为初始状态开始递推，此时公共子序列都为0。
对于text1[i - 1]和text2[j - 1]，可以分为两种情况分析：

* 当i = 7; j = 3;时，text1[i - 1]和text2[j - 1]相等，都为e。当前状态dp[i][j]由dp[i - 1][j - 1]，也就是子串xabccd和ac的结果加 1 而来，因此递推公式为：dp[i][j] = dp[i - 1][j - 1] + 1;。

* 当i = 6; j = 2;时，text1[i - 1] = 'd'，text2[j - 1] = 'c'，两者不相等。但此时他们的两对子串分别为：

* xabccd与a，子序列数量为 1。

* xabcc与ac，子序列数量为 2。

因此xabccd与ac的子序列即为两者中较大值 2，状态转移方程为：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

/** * @param {string} text1 * @param {string} text2 * @return {number} */var longestCommonSubsequence = function (text1, text2) {  // 分别缓存两个字符串的长度  const m = text1.length;  const n = text2.length;  // 初始化DP数组，默认值为第一行，对应text1为空字符串的情况，初始值都为0  let dp = [new Array(n + 1).fill(0)];
  // 遍历text1  for (let i = 1; i <= m; i++) {    // 存入当前行的状态，第一列对应了text2为空字符串的情况，初始值都为0    dp.push(new Array(n + 1).fill(0));
    // 遍历text2    for (let j = 1; j <= n; j++) {      // 如果当前字母相等，当前位置一定可以加1，那么只需从text1[0]到text1[i-2]和text2[0]到text2[j-2]的公共子序列推导到此处即可      if (text1[i - 1] === text2[j - 1]) {        dp[i][j] = dp[i - 1][j - 1] + 1;      } else {        // 当前字母不相等        // 但从text1[0]到text1[i - 1]与text2[0]到text2[j - 2]，或者从text1[0]到text1[i - 2]与text2[0]到text2[j - 1]进行对比的话，都可能会出现公共子序列        // 由于涉及到两种情况，此处需要取最大值        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);      }    }  }
  // 推导完两个字符串长度，最后得到的就是最长公共子序列  return dp[m][n];};

复制代码

发布于: 2021 年 02 月 19 日阅读数: 17

原文链接:【http://xie.infoq.cn/article/306f57eb1cd5a601b0115f36d】。文章转载请联系作者。

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

发布

暂无评论

创作场景

LeetCode 题解：1143. 最长公共子序列，动态规划，JavaScript，详细注释

Lee Chen

评论