查找最长公共子序列

一个经常被当作编程挑战问题的动态规划问题是最长公共子序列（LCS）：找出两个字符串序列的最长子序列的长度。最长子序列是指，在两个字符串序列中以相同顺序出现，但不要求连续（非字符串子串）的字符串序列。

问题

一个字符串被称为另一个字符串的子序列串，如果它可以通过从另一个字符串中删除零个或多个字符来形成。字母不能重新排列。给定两个字符串，找出可以同时成为两者最长公共子序列的长度。

HackerRank 中的原问题是给定两个等长的字符串。其实，是否等长不影响具体实现。

例子：

s1 = 'ABCD'
s2 = 'ABDC'

对于字符串 ABCD 和 ABDC，它们有两个最长子序列，即 ABC 和 ABD。这两个字符串可以通过从两者中分别删除 D 或 C 来形成。运行代码返回结果长度为 3。

int：输入字符串的最长公共子序列的长度

如何用 JavaScript 解答这个问题？

ChatGPT 的方案

在 ChatGPT 中输入上述问题指令将得到以下解答：

你可以使用动态规划来实现找到两个字符串的最长公共子序列的长度。创建一个二维数组来存储每对子序列的公共子序列的长度。以下是 JavaScript 的实现：

function commonChild(s1, s2) {
  const m = s1.length;
  const n = s2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[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];
}

// 示例用法：
console.log(commonChild('abcdefg', 'acef')) // 输出 4 ✅
console.log(commonChild('ABCD', 'ABDC')) // 输出 3 ✅
console.log(commonChild("ABCDF", "FBDAMN")); // 输出 2 ✅
console.log(commonChild("ABDFBF", "FBDABD")); // 输出 3 ✅

在这个实现中，dp 数组是一个二维数组，其中 dp[i][j] 表示子字符串 s1.substring(0, i) 和 s2.substring(0, j) 的公共子序列的长度。动态规划的方法高效地填充了这个数组，最终结果存储在 dp[m][n] 中，表示最长的公共子序列的长度。

解释不多，测试全通过。😄

这个方法的时间复杂度为 O(m * n)，其中 m 和 n 分别是两个字符串的长度。

文心一言的方案

在文心一言中输入ChatGPT 相同的问题指令将得到以下解答：

这个问题可以通过动态规划（Dynamic Programming）来解决。我们可以创建一个二维数组 dp，其中 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的最长公共子序列串的长度。然后我们可以使用下面的递推关系来填充这个数组：

如果 s1[i-1] === s2[j-1]，那么 dp[i][j] = dp[i-1][j-1] + 1。也就是说，如果 s1 的第 i 个字符和 s2 的第 j 个字符相等，那么最长公共子序列的长度就是 s1 的前 i - 1 个字符和 s2 的前 j - 1 个字符的最长公共子序列的长度加 1。
如果 s1[i-1] !== s2[j-1]，那么 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])。也就是说，如果 s1 的第 i 个字符和 s2 的第 j 个字符不相等，那么最长公共子序列的长度就是 s1 的前 i - 1 个字符和 s2 的前 j 个字符的最长公共子序列的长度，以及 s1 的前 i 个字符和 s2 的前 j - 1 个字符的最长公共子序列的长度的较大值。
最后，dp[s1.length][s2.length] 就是我们的答案，也就是 s1 和 s2 的最长公共子序列的长度。

解释很多，代码和 ChatGPT 提供的一模一样，测试也全通过。😄

示例用法：

console.log(commonChild('abcdefg', 'acef')) // 输出 4 ✅
console.log(commonChild('ABCD', 'ABDC')) // 输出 3 ✅
console.log(commonChild("ABCDF", "FBDAMN")); // 输出 2 ✅
console.log(commonChild("ABDFBF", "FBDABD")); // 输出 3 ✅

搜索 AI 伙伴的方案

更多时候在百度搜索框输入代码问题时会引导我们使用 AI 伙伴。以下是在输入ChatGPT 相同问题后的解答：

要解决这个问题，可以使用动态规划的方法。我们可以创建一个二维数组 dp，其中 dp[i][j] 表示 s1的前 i 个字符和 s2 的前 j 个字符的最长公共子序列的长度。

首先，初始化 dp 数组的所有值为 0。然后，我们遍历 s1 和 s2 的所有字符，对于每个字符，我们检查它是否相同。如果相同，则更新 dp[i][j] 的值为 dp[i-1][j-1] + 1（因为我们可以将当前字符添加到最长公共子序列中）。如果不同，则 dp[i][j] 的值保持不变。

最后，dp[s1.length][s2.length] 就是我们要找的最长公共子序列的长度。

以下是使用JavaScript实现的代码：

function commonChild(s1, s2) {
    const m = s1.length;
    const n = s2.length;
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s1[i - 1] === s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
        }
    }
    
    return dp[m][n];
}

你可以使用这个函数来计算两个字符串的最长公共子序列的长度。例如：

示例用法：

console.log(commonChild('abcdefg', 'acef')) // 输出 0 ❌
console.log(commonChild('ABCD', 'ABDC')) // 输出 0 ❌
console.log(commonChild("ABCDF", "FBDAMN")); // 输出 0 ❌
console.log(commonChild("ABDFBF", "FBDABD")); // 输出 0 ❌