LeetCode 1092. 最短公共超序列

2023-04-15 HGNULB 约 10 分钟

文章信息 8 个分类 3 个标签

分类

题目描述

✅ 1092. 最短公共超序列

题意分析

给定两个字符串 str1 和 str2，要构造一个尽可能短的字符串，使得 str1 和 str2 都是它的子序列。子序列允许不连续但必须保序，所以答案里两个串的字符相对次序都不能被打乱。

题目要的是字符串本身，不是长度。这一点决定了只算出一个数值是不够的，必须保留足够的信息把答案一个字符一个字符地拼出来。

约束里两个串长度都不超过 $1000$，且只含小写字母。平方级的做法完全能过，而指数级地枚举「哪些位置共用」则不可能。同时题目明确说明答案可能不唯一，只要长度最短即可，这意味着遇到并列的选择时可以任取一支。

边界要提前想清楚：两串完全相同时答案就是它本身；两串没有任何公共字符时答案只能是两串首尾相接；某个串是另一个串的子序列时答案就是较长的那个串。这三种情况必须都能被同一套逻辑覆盖。

解法：LCS 辅助重建

核心思路

最直接的想法是枚举所有可能的超序列并取最短，但长度上限就是 $m + n$，候选数量随长度指数增长，无法承受。瓶颈在于「哪些字符被两个串共用」这件事被当成了自由组合去枚举。

换个角度看长度。设答案长度为 $L$，答案里的每个字符要么只服务 str1，要么只服务 str2，要么被两者共用。把共用的字符按出现顺序取出来，它在 str1 中保序出现，在 str2 中也保序出现，所以它必然是两串的一个公共子序列。反过来，任意一个公共子序列都能用来拼一个合法的超序列。于是 $L = m + n - (\text{共用字符数})$，要让 $L$ 最小，就要让共用字符数最大，也就是求最长公共子序列。

状态定义如下：dp[i][j] 表示 str1 从下标 i 开始的后缀与 str2 从下标 j 开始的后缀的最长公共子序列长度。这里刻意选后缀而不是前缀，是因为重建阶段要从头往后逐字符输出，站在位置 (i, j) 时需要知道的是「往后还能共享多少」，后缀定义正好回答这个问题。

转移遵循两条：若 str1[i] == str2[j]，这个字符一定可以被共用，dp[i][j] = dp[i + 1][j + 1] + 1；否则这两个字符至少有一个不能被共用，dp[i][j] 取跳过其中之一的较大值。边界是任一串走完时后缀公共子序列长度为 $0$。

解题步骤

建立 $(m + 1) \times (n + 1)$ 的二维数组 dp，多出来的一行一列天然为 $0$，正好承担「某个串已经走完」的边界，省掉了单独的判空分支。

双层循环让 i 从 $m - 1$ 递减到 $0$、j 从 $n - 1$ 递减到 $0$。必须倒序，因为 dp[i][j] 依赖 dp[i + 1][j + 1]、dp[i + 1][j]、dp[i][j + 1]，这三个都是下标更大的格子，正序会读到尚未计算的零值。

从 i = 0、j = 0 开始重建。之所以能贪心地一步步定，是因为 dp 已经把「从当前位置往后的最优解」全部算好，每一步的局部选择不会影响后续的最优性。

若 str1[i] == str2[j]，说明这个字符可以被两个串共用，只往结果里追加一次，然后 i 和 j 同时前进，共用一个字符正好省下一格长度。

若两字符不同，就必须先输出其中一个。比较 dp[i + 1][j] 和 dp[i][j + 1]：前者代表消耗掉 str1[i] 之后剩余部分还能共享的字符数。哪一侧留下的共享空间更大就走哪一侧，这样才不会为了眼前少写一个字符而破坏后面更长的共用段。

循环退出时至少有一个串已走完，把 str1 和 str2 各自的剩余后缀都追加到结果末尾。两者中必有一个为空串，所以直接都追加不会出错，也省掉了判断是哪一侧走完。

以 str1 = "abac"、str2 = "cab" 走一遍：先填 dp，第 4 行与第 3 列全为 $0$。i = 3 时字符是 c，dp[3][2] = 0、dp[3][1] = 0、dp[3][0] = dp[4][1] + 1 = 1。i = 2 时字符是 a，dp[2][2] = 0、dp[2][1] = dp[3][2] + 1 = 1、dp[2][0] = max(1, 1) = 1。i = 1 时字符是 b，dp[1][2] = dp[2][3] + 1 = 1、dp[1][1] = max(1, 1) = 1、dp[1][0] = max(1, 1) = 1。i = 0 时字符是 a，dp[0][2] = max(1, 0) = 1、dp[0][1] = dp[1][2] + 1 = 2、dp[0][0] = max(dp[1][0], dp[0][1]) = max(1, 2) = 2。所以最长公共子序列长度为 $2$，答案长度应为 $4 + 3 - 2 = 5$。

接着重建。i = 0、j = 0 时 a 与 c 不同，dp[1][0] = 1 小于 dp[0][1] = 2，走 str2 一侧，追加 c，j 变为 $1$，结果为 "c"。i = 0、j = 1 时 a 与 a 相同，追加 a，i 变为 $1$、j 变为 $2$，结果为 "ca"。i = 1、j = 2 时 b 与 b 相同，追加 b，i 变为 $2$、j 变为 $3$，结果为 "cab"。此时 j 已达 n，循环结束。追加 str1 的剩余后缀 "ac" 得到 "cabac"，追加 str2 的剩余后缀为空串。最终返回 "cabac"，长度为 $5$，且 str1 与 str2 都是它的子序列。

代码实现

class Solution {
    // 先用 DP 求 LCS 长度，再沿着 DP 表重建答案，可以决定当前应该追加哪个字符串的字符。
    public String shortestCommonSupersequence(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (str1.charAt(i) == str2.charAt(j)) {
                    dp[i][j] = dp[i + 1][j + 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }

        StringBuilder answer = new StringBuilder();
        int i = 0;
        int j = 0;
        while (i < m && j < n) {
            if (str1.charAt(i) == str2.charAt(j)) {
                answer.append(str1.charAt(i));
                i++;
                j++;
            } else if (dp[i + 1][j] >= dp[i][j + 1]) {
                answer.append(str1.charAt(i));
                i++;
            } else {
                answer.append(str2.charAt(j));
                j++;
            }
        }

        answer.append(str1.substring(i));
        answer.append(str2.substring(j));
        return answer.toString();
    }
}

func shortestCommonSupersequence(str1 string, str2 string) string {
    // 先用 DP 求 LCS 长度，再沿着 DP 表重建答案，可以决定当前应该追加哪个字符串的字符。
    m, n := len(str1), len(str2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            if str1[i] == str2[j] {
                dp[i][j] = dp[i+1][j+1] + 1
            } else if dp[i+1][j] >= dp[i][j+1] {
                dp[i][j] = dp[i+1][j]
            } else {
                dp[i][j] = dp[i][j+1]
            }
        }
    }

    answer := make([]byte, 0, m+n)
    i, j := 0, 0
    for i < m && j < n {
        if str1[i] == str2[j] {
            answer = append(answer, str1[i])
            i++
            j++
        } else if dp[i+1][j] >= dp[i][j+1] {
            answer = append(answer, str1[i])
            i++
        } else {
            answer = append(answer, str2[j])
            j++
        }
    }

    answer = append(answer, str1[i:]...)
    answer = append(answer, str2[j:]...)
    return string(answer)
}

复杂度分析

时间复杂度：$O(mn)$，其中 m、n 是两个字符串的长度。填表阶段每个格子做常数次比较与取最大值，共 $mn$ 个格子；重建阶段每一步至少让 i 或 j 前进一格，最多走 $m + n$ 步，相比填表可以忽略。

空间复杂度：$O(mn)$，二维表必须整张保留才能在重建时反查每个位置的后缀最优值，因此不能压缩成滚动数组；返回的结果串另占 $O(m + n)$，不计入辅助空间。

关键点总结

把「最短超序列」翻译成「最长公共子序列」是本题的核心一跃：长度关系 $L = m + n - \text{LCS}$ 把一个构造问题转化成了标准的计数型动态规划，最小化目标变成了最大化目标。

需要输出方案而不只是数值时，动态规划表要按「便于回溯的方向」定义。这里选后缀而非前缀，就是为了让从前往后的重建能直接查表，避免先算前缀再倒着回溯、还要把结果反转的额外一步。

用 $(m + 1) \times (n + 1)$ 的表把边界并入数组，是二维字符串动态规划的通用技巧，能把「某串已走完」的特判彻底消灭在初始化里。

重建时并列的分支任取一支即可，这类「答案不唯一」的题目要先确认判题方式，避免把自己的输出和示例逐字符比对而误以为写错了。

面试视角：面试官问这题，真正想看的是你能否说出长度公式的推导，而不是背下转移方程。先讲清「共用字符必是公共子序列」，再自然过渡到需要输出方案、所以要留整张表，最后才写代码，这个叙述顺序比直接默写更有说服力。

面试视角：被追问优化时，要能准确指出只求长度可以压成一维滚动数组做到 $O(\min(m, n))$ 空间，但本题要输出方案就必须保留整张表，这个取舍点是常见的加分回答。

易错点总结

错误写法：把 dp 定义成前缀的最长公共子序列，却仍从 i = 0、j = 0 正向重建 → 此时 dp[i + 1][j] 描述的是前缀信息，和「往后还能共享多少」无关，重建的分支判断失去依据，"abac" 与 "cab" 会输出长度大于 $5$ 的串。

错误写法：填表时让 i、j 从 $0$ 递增 → dp[i][j] 依赖的 dp[i + 1][j + 1] 等格子还没算，全部读到 $0$，最终 dp[0][0] 恒为 str1[0] == str2[0] ? 1 : 0，长度公式直接失效。

错误写法：数组只开成 int[m][n] → 循环里访问 dp[i + 1][j + 1]，当 i 取 $m - 1$ 时立即数组越界，抛出下标异常。

错误写法：两字符相同时往结果里追加两次 → 共用字符被重复写入，"abac" 与 "cab" 得到的串长度大于 $5$，虽然仍是合法超序列但不是最短，判题会失败。

错误写法：循环结束后只追加 str1 的剩余后缀，忘了 str2 → 当 str1 先走完时 str2 的尾部整段丢失，返回的串不再包含 str2 作为子序列。

错误写法：两字符不同时比较 dp[i][j] 与某个相邻值来决定方向 → dp[i][j] 已经是两条分支的最大值，和自己的子项比较无法区分该消耗哪一侧，方向选择退化成固定偏好，长度不再最短。

错误写法：只算出最长公共子序列长度就返回 m + n - len → 题目要求返回超序列字符串本身，返回长度会直接判类型错误。

错误写法：在循环中用字符串加法拼接结果 → 每次追加都复制一遍已有内容，长度上千时产生大量中间字符串，运行时间成倍上升，应当用可变的字符缓冲区累积。

错误写法：假设某个串为空要单独返回另一个串 → 题目保证两串长度都至少为 $1$，多写的特判本身无害，但若把判空条件写成长度为 $0$ 之外的形式反而会误触发，返回不完整的答案。

相似题目

题目	难度	考察点
1143. 最长公共子序列	中等	本题的内核，只求长度不需重建，可压成一维滚动数组
72. 编辑距离	中等	同样的二维格局，但转移里多出替换操作，求最小代价而非最大共享
583. 两个字符串的删除操作	中等	求删除步数，答案是 $m + n - 2 \times \text{LCS}$，与本题公式互为镜像
1035. 不相交的线	中等	把连线不交叉的几何约束翻译成公共子序列，考察问题建模
712. 两个字符串的最小ASCII删除和	中等	从计数改为按字符权重求和，不能再套长度公式