#1143.最长公共子序列

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
解释：两个字符串没有公共子序列。

#提示

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字母组成

#1.dp 数组含义

定义二维数组 dp：

dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度。

这里的 i 和 j 表示前缀长度，不是字符串下标。例如 dp[3][2] 表示 text1 的前 3 个字符和 text2 的前 2 个字符的答案。

题目要求整个字符串的最长公共子序列长度，所以最终答案是：

dp[text1.length][text2.length]

#2. 确定状态转移方程

计算 dp[i][j] 时，比较两个前缀的最后一个字符：

text1[i - 1]
text2[j - 1]

#当前字符相同

如果 text1[i - 1] === text2[j - 1]，当前字符可以作为公共子序列的最后一个字符：

dp[i][j] = dp[i - 1][j - 1] + 1;

#当前字符不同

如果两个字符不同，它们不能同时作为当前公共子序列的最后一个字符。可以分别跳过 text1 或 text2 的当前字符，并取两种情况的较大值：

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

完整转移方程：

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]);
}

#3.dp 数组如何初始化

dp[0][j] = 0：空字符串和任意字符串没有公共子序列。

dp[i][0] = 0：任意字符串和空字符串没有公共子序列。

因此创建 (text1.length + 1) * (text2.length + 1) 的数组，并全部初始化为 0。这也自然覆盖了任意一个输入字符串为空的情况。

#4. 确定遍历顺序

dp[i][j] 依赖左上方的 dp[i - 1][j - 1]、上方的 dp[i - 1][j] 和左侧的 dp[i][j - 1]，所以 i、j 都从 1 开始正序遍历：

for (let i = 1; i <= m; i++) {
  for (let j = 1; j <= n; j++) {
    // 计算 dp[i][j]
  }
}

#5. 举例打印dp 数组

以 text1 = "abcde"、text2 = "ace" 为例：

例如：

• dp[1][1] = dp[0][0] + 1 = 1，因为 a === a。
• dp[2][2] = Math.max(dp[1][2], dp[2][1]) = 1，因为 b !== c。
• dp[5][3] = dp[4][2] + 1 = 3，因为 e === e。

最终答案为 dp[5][3] = 3，最长公共子序列是 "ace"。

#6. 代码实现

var longestCommonSubsequence = function (text1, text2) {
  const m = text1.length;
  const n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => 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];
};