LeetCode 1143. 最长公共子序列

约 5 分钟
文章信息 26 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 需加强 100-200 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 拼多多 网易 小米 商汤 虾皮 携程 小红书 LeetCode 75 LeetCode 热题 100
标签
字符串 动态规划 子序列问题 最长公共子序列
目录

题目描述

✅ 1143. 最长公共子序列

image-20220921002108483

题意分析

输入两个字符串 text1 和 text2，要求返回它们最长公共子序列的长度。子序列的定义是「删掉原串中任意个（含零个）字符、不改变剩余字符相对顺序」得到的串，因此公共子序列不必连续，但必须保序。

「不必连续」和「必须保序」这两条一起把问题钉死了：它不是求公共子串（那要求位置连续），也不是求公共字符的多重集大小（那完全不管顺序）。判断一个思路对不对，最快的办法就是拿 "ab" 和 "ba" 试——它们有两个公共字符，但最长公共子序列只有 1。

题目只要长度，不要求输出具体的子序列，所以不需要记录路径。另一个关键信号是这里同时有两个串：任何时刻都要同时说清「text1 消耗到了哪里」和「text2 消耗到了哪里」，只报其中一个位置无法描述局面，两个进度是互相独立的两个维度。它要求的又是「最长」，说明每一对下标上都存在「用还是不用」的选择，且这些选择之间会互相制约：一旦决定在某两个位置上配对，后面的配对就只能发生在这两个位置之后。

需要单独想清楚的边界：任意一个串为空时答案是 0；两串完全相同时答案是串长；两串没有任何公共字符时答案是 0；同一个字符在串里重复出现是允许的，配对时不能因为「这个字符已经用过」就跳过。

解法：一维动态规划

核心思路

dp[j] 表示当前遍历到 text1 某个前缀时，它与 text2[:j] 的最长公共子序列长度。字符相同就取上一行左上角加一；不同就取上方和左方的较大值。用 diagonal 保存被覆盖的左上角状态，可把二维表压成一行。

解题步骤

  • 将较短字符串放在内层，创建长度为 n + 1 的一维数组。
  • 每行开始令 diagonal = 0，它表示二维表的左上角旧值。
  • 从左到右更新 dp[j]：字符相同取 diagonal + 1，否则取 max(dp[j], dp[j - 1])。
  • 覆盖前保存旧 dp[j]，本轮结束后交给下一列作为 diagonal。

代码实现

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        if (text1.length() < text2.length()) {
            String temp = text1;
            text1 = text2;
            text2 = temp;
        }

        int[] dp = new int[text2.length() + 1];
        for (int i = 1; i <= text1.length(); i++) {
            int diagonal = 0;
            for (int j = 1; j <= text2.length(); j++) {
                int up = dp[j];
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[j] = diagonal + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                diagonal = up;
            }
        }
        return dp[text2.length()];
    }
}

func longestCommonSubsequence(text1 string, text2 string) int {
    if len(text1) < len(text2) {
        text1, text2 = text2, text1
    }

    dp := make([]int, len(text2)+1)
    for i := 1; i <= len(text1); i++ {
        diagonal := 0
        for j := 1; j <= len(text2); j++ {
            up := dp[j]
            if text1[i-1] == text2[j-1] {
                dp[j] = diagonal + 1
            } else if dp[j-1] > dp[j] {
                dp[j] = dp[j-1]
            }
            diagonal = up
        }
    }
    return dp[len(text2)]
}

复杂度分析

  • 时间复杂度：$O(mn)$，m、n 为两个字符串的长度。
  • 空间复杂度：$O(\min(m, n))$，只保存较短字符串对应的一行状态。

关键点总结

  • 状态表示两个前缀的最长公共子序列长度，而不是最长公共子串。
  • 字符相同时同时缩短两个前缀；不同时只舍弃其中一个末尾字符。
  • 一维压缩时，dp[j] 是上方旧值，dp[j - 1] 是左方新值，diagonal 是左上角旧值。

易错点总结

  • dp 下标表示前缀长度，访问字符时必须减一。
  • 必须在覆盖 dp[j] 前保存旧值，否则下一列会丢失左上角状态。
  • 内层循环必须从左到右，且每行都要把 diagonal 重置为 0。

相似题目

题目 难度 考察点
72. 编辑距离 中等 同一张表求最小代价，字符不同时要加一并多出「替换」这一个来源
97. 交错字符串 中等 状态值从「最大长度」变成「是否可行」，转移取或而不是取最大值
516. 最长回文子序列 中等 只有一个串，等价于它与自身反转串求本题；也可直接用区间 DP，枚举顺序变成按长度
583. 两个字符串的删除操作 中等 答案是两串长度和减去两倍本题结果，考的是把删除次数翻译成保留长度
712. 两个字符串的最小ASCII删除和 中等 每个字符的权重不再是 1 而是 ASCII 值，最大化保留权重而不是保留个数
718. 最长重复子数组 中等 要求连续，字符不同时必须归零，答案取全表最大值而不是右下角
1035. 不相交的线 中等 换成两行数字连线，剥掉几何外壳后与本题完全同构，考的是识别模型
LCR 095. 最长公共子序列 中等 与本题同题，可用来分别默写二维与滚动两版并对照中间状态
LCR 096. 交错字符串 中等 与 97 同题，第三个串的下标由前两个之和唯一确定，状态维度反而更少