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

[chencl1986]

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

解题思路：

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

图片来自：C++ with picture, O(nm)。

1. 假设text1长度为m，索引为i。text2长度为n，索引为j。
2. 公共子序列要判断每个字母是否相等，dp[i][j]的状态必须由dp[i - 1][j - 1]推导而来，因此我们可以创建一个(m + 1) * (n + 1)的矩阵。将索引0的位置，即空字符串作为初始状态开始递推，此时公共子序列都为0。
3. 对于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];
};