1143.最长公共子序列

难度：🟡 中等

标签：字符串、动态规划

链接：1143. 最长公共子序列

题目描述

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

解题思路

核心思想

本题的目标是找到两个字符串的“最长”“公共”“子序列”的长度。这是一个非常经典的二维动态规划问题。核心思想是通过构建一个二维 dp 表来记录中间结果，从而解决整个问题。

思路选择

动态规划 (Dynamic Programming) 是解决此问题的标准最优思路。

• 我们可以定义一个二维 dp 数组（或表格），其中 dp[i][j] 表示 text1 的前 i 个字符（即 text1[0..i-1]）与 text2 的前 j 个字符（即 text2[0..j-1]）的最长公共子序列的长度。

• 状态转移 的逻辑如下：

  1. 如果 text1[i-1] 与 text2[j-1] 相等，说明这个字符可以作为公共子序列的一部分。因此，当前的最长公共子序列长度就是它们各自前一个状态的最长公共子序列长度加一，即 dp[i][j] = dp[i-1][j-1] + 1。

  2. 如果 text1[i-1] 与 text2[j-1] 不相等，说明这个字符不能同时作为结尾。此时，dp[i][j] 的值应该取决于两种情况的较大者：

     • text1 的前 i-1 个字符与 text2 的前 j 个字符的最长公共子序列长度（即 dp[i-1][j]）。

     • text1 的前 i 个字符与 text2 的前 j-1 个字符的最长公共子序列长度（即 dp[i][j-1]）。 所以，dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])。

关键步骤

1. 初始化：创建一个 (m+1) x (n+1) 的 dp 数组，并全部填充为 0，其中 m 和 n 分别是 text1 和 text2 的长度。

2. 双层循环： a. 外层循环遍历 i 从 1 到 m。 b. 内层循环遍历 j 从 1 到 n。

3. 状态转移：在循环内部，根据 text1[i-1] 和 text2[j-1] 是否相等，应用上述的状态转移方程来填充 dp[i][j]。

4. 返回结果：遍历结束后，dp[m][n] 的值就是 text1 和 text2 的最长公共子序列的长度。

代码实现

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
    const m = text1.length, n = text2.length;
    // dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列长度
    const dp = new Array(m + 1).fill(null).map(() => 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]);
            }
        }
    }

    // 最终结果存储在 dp 表的右下角
    return dp[m][n];
};

复杂度分析

• 时间复杂度：O(m × n) 其中 m 和 n 分别是两个字符串的长度。我们需要填充整个 dp 表。

• 空间复杂度：O(m × n) 我们需要一个二维数组来存储 dp 表。可以通过状态压缩将空间复杂度优化到 O(min(m, n))。

相关题目

• 0005.最长回文子串

• 0300.最长递增子序列

• 0072.编辑距离

总结

本题是二维动态规划最经典、最基础的题目之一。其状态定义 dp[i][j] 和状态转移方程的设计模式，是解决一系列字符串匹配、序列比对问题的通用模板。深刻理解其递推关系是掌握动态规划的关键。