最短公共超序列 图解题解

这道题到底在问什么

输入

str1 = "abac", str2 = "cab"

输出

"cabac"(长度 5,两串都能从中跳着取出来)

输入

str1 = "abc", str2 = "abc"

输出

"abc"(完全相同,不用补任何字符)

输入

str1 = "abc", str2 = "def"

输出

"abcdef"(毫无公共字符,只能拼起来)

最优解：一步一步想明白

1. 3一句话套路:最短超序列 = 把 LCS 当骨架,公共字符只写一次、独有字符按原序补入。先填 dp 表求 LCS,再沿表重构。
2. 4先搭骨架:行对应 str1「abac」的字符,列对应 str2「cab」的字符,行列末尾各加一格 ∅ 代表「空后缀」。dp[i][j] 表示 str1 第 i 个起的后缀 与 str2 第 j 个起的后缀 的 LCS 长度,现在全是「·」表示还没算。我们从右下往左上填。
3. 5最下面一行是 str1 的空后缀:空串和任何串的 LCS 都是 0,整行填 0(紫格)。它是后面所有格往下看时的地基。
4. 6最右边一列是 str2 的空后缀:同理 LCS 都是 0,整列填 0(紫格)。基础格备齐,接下来从右下角内部一格格往左上推。
5. 7看 "c" 和 "b":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[4][2]=0(跳过 str1 这个字符),右方 dp[3][3]=0(跳过 str2 这个字符),取较大 = 0(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。
6. 8看 "c" 和 "a":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[4][1]=0(跳过 str1 这个字符),右方 dp[3][2]=0(跳过 str2 这个字符),取较大 = 0(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。
7. 9看 "c"(str1 第 4 个)和 "c"(str2 第 1 个):相同!这个字符能进 LCS,长度 = 右下角 dp[4][1]=0 再加 1 = 1(紫格,蓝格是它依赖的右下角)。
8. 10看 "a" 和 "b":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[3][2]=0(跳过 str1 这个字符),右方 dp[2][3]=0(跳过 str2 这个字符),取较大 = 0(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。
9. 11看 "a"(str1 第 3 个)和 "a"(str2 第 2 个):相同!这个字符能进 LCS,长度 = 右下角 dp[3][2]=0 再加 1 = 1(紫格,蓝格是它依赖的右下角)。
10. 12看 "a" 和 "c":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[3][0]=1(跳过 str1 这个字符),右方 dp[2][1]=1(跳过 str2 这个字符),取较大 = 1(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。
11. 13看 "b"(str1 第 2 个)和 "b"(str2 第 3 个):相同!这个字符能进 LCS,长度 = 右下角 dp[2][3]=0 再加 1 = 1(紫格,蓝格是它依赖的右下角)。
12. 14看 "b" 和 "a":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[2][1]=1(跳过 str1 这个字符),右方 dp[1][2]=1(跳过 str2 这个字符),取较大 = 1(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。
13. 15看 "b" 和 "c":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[2][0]=1(跳过 str1 这个字符),右方 dp[1][1]=1(跳过 str2 这个字符),取较大 = 1(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。
14. 16看 "a" 和 "b":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[1][2]=1(跳过 str1 这个字符),右方 dp[0][3]=0(跳过 str2 这个字符),取较大 = 1(下方更长,蓝格是两个依赖)。
15. 17看 "a"(str1 第 1 个)和 "a"(str2 第 2 个):相同!这个字符能进 LCS,长度 = 右下角 dp[1][2]=1 再加 1 = 2(紫格,蓝格是它依赖的右下角)。
16. 18看 "a" 和 "c":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[1][0]=1(跳过 str1 这个字符),右方 dp[0][1]=2(跳过 str2 这个字符),取较大 = 2(右方更长,蓝格是两个依赖)。
17. 19整张表填满。左上角 dp[0][0] = 2,意思是 "abac" 与 "cab" 的最长公共子序列长度为 2(正是 "ab")。LCS 这副骨架有了,下面沿着 dp 表从左上角走一遍,把答案重构出来。
18. 20重构规则:站在格子 (i, j),① 若 str1[i]=str2[j],这是公共字符,只写一次,i、j 同时右下移;② 若不同,跟着「LCS 更长」的那一边走,把被跳过那一侧的独有字符先写进答案。指针从 (0,0) 出发。
19. 21当前 (0,0):"a" 与 "c" 不同。右方 LCS 2 更大,跟着右方走,要跳过 str2 的 "c",把这个 str2 独有字符先补进答案,只 j++(蓝格往右)。答案现在是 "c"。
20. 22当前 (0,1):"a" 两边相同,是公共字符,只写一次 "a" 进答案,然后 i、j 一起往右下走(绿格表示已落定)。答案现在是 "ca"。
21. 23当前 (1,2):"b" 两边相同,是公共字符,只写一次 "b" 进答案,然后 i、j 一起往右下走(绿格表示已落定)。答案现在是 "cab"。
22. 24指针有一边走到了头(到了 ∅ 边界),剩下另一边的字符不会再有公共部分,原样全部接上即可。这里 str1 还剩 "ac"、str2 还剩 "空",接上后答案 = "cabac"。
23. 25复盘:LCS "ab" 是公共骨架只写一次,str2 独有的 "c" 在前面补、str1 独有的 "ac" 在后面补,拼成 "cabac"。验证一下:从它里能跳取出 "abac"(原 str1)和 "cab"(原 str2),且长度 = str1 长 4 + str2 长 3 − LCS 长 2 = 5,无法更短。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if str1[i] == str2[j]:
                    dp[i][j] = dp[i + 1][j + 1] + 1
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
        i = j = 0
        ans = []
        while i < m and j < n:
            if str1[i] == str2[j]:
                ans.append(str1[i]); i += 1; j += 1
            elif dp[i + 1][j] >= dp[i][j + 1]:
                ans.append(str1[i]); i += 1
            else:
                ans.append(str2[j]); j += 1
        ans.append(str1[i:]); ans.append(str2[j:])
        return ''.join(ans)

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        int m = str1.size(), n = str2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = m - 1; i >= 0; --i) for (int j = n - 1; j >= 0; --j)
            dp[i][j] = str1[i] == str2[j] ? dp[i+1][j+1] + 1 : max(dp[i+1][j], dp[i][j+1]);
        int i = 0, j = 0;
        string ans;
        while (i < m && j < n) {
            if (str1[i] == str2[j]) { ans.push_back(str1[i]); i++; j++; }
            else if (dp[i+1][j] >= dp[i][j+1]) ans.push_back(str1[i++]);
            else ans.push_back(str2[j++]);
        }
        ans += str1.substr(i) + str2.substr(j);
        return ans;
    }
};

import java.util.*;
class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int m = str1.length(), 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--)
            dp[i][j] = str1.charAt(i) == str2.charAt(j) ? dp[i + 1][j + 1] + 1 : Math.max(dp[i + 1][j], dp[i][j + 1]);
        int i = 0, j = 0;
        StringBuilder ans = new StringBuilder();
        while (i < m && j < n) {
            if (str1.charAt(i) == str2.charAt(j)) { ans.append(str1.charAt(i)); i++; j++; }
            else if (dp[i + 1][j] >= dp[i][j + 1]) ans.append(str1.charAt(i++));
            else ans.append(str2.charAt(j++));
        }
        ans.append(str1.substring(i)).append(str2.substring(j));
        return ans.toString();
    }
}

复杂度

面试官可能追问