§1

题目描述

给定 str1 和 str2,返回一个最短的字符串,使 str1 和 str2 都是它的子序列(子序列指保持相对顺序、可以跳过若干字符)。

输入 = str1 = "abac", str2 = "cab"　输出 = "cabac"(长度 5,两串都能从中跳着取出来)

输入 = str1 = "abc", str2 = "abc"　输出 = "abc"(完全相同,不用补任何字符)

输入 = str1 = "abc", str2 = "def"　输出 = "abcdef"(毫无公共字符,只能拼起来)

§2

思路解析

一句话答案：LeetCode 1092 最短公共超序列：让 str1、str2 都成为它子序列的最短串。先填 dp 表求最长公共子序列 LCS 当骨架，再沿表重构、公共字符只写一次，时间 O(mn)、空间 O(mn)。

最短公共超序列到底要拼出哪个串

给两个字符串 str1 和 str2，找一个最短的串，让两者都是它的子序列（子序列 = 保持相对顺序、可跳字符取出）。例子 str1 = "abac"、str2 = "cab" 的答案是 "cabac"。

为什么直接把两串拼起来不算最短

把 str1 直接接上 str2 得到长度 m + n 的串（m、n 为两串长度），合法但不最短：共有的字符白写了两遍，本该只出现一次。逐条枚举所有超序列挑最短也不行，长度稍大，分支就指数级膨胀。

最长公共子序列凭什么是这题的骨架

能省的正是两串的公共部分：这些字符在 str1、str2 里各按自身顺序排着，可共用、只写一次。问题于是落到最长公共子序列（LCS，两串里都按原顺序出现、可跳字符的最长那段）——答案长度 = m + n − LCS 长度。

求 LCS 用动态规划（把两串每段后缀的 LCS 长度算一次存下、后面直接取）；后缀=从某个位置到结尾的那一段。这是一张两维的表、行对 str1 列对 str2：dp[i][j]（i、j 是 str1、str2 从 0 数起的下标）= str1 第 i 个、str2 第 j 个字符起两段后缀的 LCS 长度，(m+1) 行 (n+1) 列，末行末列是空后缀、填 0。

填表怎么推、回溯又怎么把公共字符并成一个

填表从右下往左上推。在 dp[i][j]：str1[i] 与 str2[j] 相同，取右下角 dp[i+1][j+1] + 1；不同，取下方 dp[i+1][j] 与右方 dp[i][j+1] 的较大值。

有了长度就能拼串：从 (0,0) 开始回溯（回溯=顺着填好的表往回走、把答案一个字一个字拼出来，不是搜索那种回溯）。若 str1[i] = str2[j]，是公共字符，只写一次、i 和 j 一起前进——公共部分合并成一个；若不同，跟 dp 值更大那侧走，把这侧独有字符写进答案。到头后把另一侧剩的字符接上。

拿 abac 和 cab 把表填出来再拼一遍

填表按上节规则推：str1[0]='a' 遇 str2[1]='a'，dp[0][1]=dp[1][2]+1=2；同理 dp[3][0]=1、dp[1][2]=1；最后 dp[0][0]=2，即两串 LCS 长度为 2。

回溯从 (0,0)：'a'≠'c'，右方 dp[0][1]=2 更大，先写 str2 的 'c' 得 "c"；(0,1) 'a'='a' 得 "ca"；(1,2) 'b'='b' 得 "cab"；str2 到头，接 str1 剩的 "ac"，得 "cabac"，长 4+3−2=5。

结尾那截尾巴忘了接，答案为什么连子序列都凑不齐

回溯到边界若忘接剩余尾巴，答案会缺掉末尾一段、连原串都跳不出来。另两处别写错：公共字符只写一次，写两遍就退回拼接；不同时得跟 LCS 更长那侧走，跟错会漏公共字符。

填表过 m×n 格、每格常数次比较，回溯最多 m + n 步，时间 O(mn)（大 O 记号 = 规模变大时操作数怎么涨），空间同样 O(mn)。回溯要任意回看格子，没法只留几行做滚动数组省空间。两串相同则答案是原串，无公共则拼接。

▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开

一句话套路:最短超序列 = 把 LCS 当骨架,公共字符只写一次、独有字符按原序补入。先填 dp 表求 LCS,再沿表重构。

先搭骨架:行对应 str1「abac」的字符,列对应 str2「cab」的字符,行列末尾各加一格 ∅ 代表「空后缀」。dp[i][j] 表示 str1 第 i 个起的后缀与 str2 第 j 个起的后缀的 LCS 长度,现在全是「·」表示还没算。我们从右下往左上填。

最下面一行是 str1 的空后缀:空串和任何串的 LCS 都是 0,整行填 0(紫格)。它是后面所有格往下看时的地基。

最右边一列是 str2 的空后缀:同理 LCS 都是 0,整列填 0(紫格)。基础格备齐,接下来从右下角内部一格格往左上推。

看 "c" 和 "b":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[4][2]=0(跳过 str1 这个字符),右方 dp[3][3]=0(跳过 str2 这个字符),取较大 = 0(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。

看 "c" 和 "a":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[4][1]=0(跳过 str1 这个字符),右方 dp[3][2]=0(跳过 str2 这个字符),取较大 = 0(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。

看 "c"(str1 第 4 个)和 "c"(str2 第 1 个):相同!这个字符能进 LCS,长度 = 右下角 dp[4][1]=0 再加 1 = 1(紫格,蓝格是它依赖的右下角)。

看 "a" 和 "b":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[3][2]=0(跳过 str1 这个字符),右方 dp[2][3]=0(跳过 str2 这个字符),取较大 = 0(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。

看 "a"(str1 第 3 个)和 "a"(str2 第 2 个):相同!这个字符能进 LCS,长度 = 右下角 dp[3][2]=0 再加 1 = 1(紫格,蓝格是它依赖的右下角)。

看 "a" 和 "c":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[3][0]=1(跳过 str1 这个字符),右方 dp[2][1]=1(跳过 str2 这个字符),取较大 = 1(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。

看 "b"(str1 第 2 个)和 "b"(str2 第 3 个):相同!这个字符能进 LCS,长度 = 右下角 dp[2][3]=0 再加 1 = 1(紫格,蓝格是它依赖的右下角)。

看 "b" 和 "a":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[2][1]=1(跳过 str1 这个字符),右方 dp[1][2]=1(跳过 str2 这个字符),取较大 = 1(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。

看 "b" 和 "c":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[2][0]=1(跳过 str1 这个字符),右方 dp[1][1]=1(跳过 str2 这个字符),取较大 = 1(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。

看 "a" 和 "b":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[1][2]=1(跳过 str1 这个字符),右方 dp[0][3]=0(跳过 str2 这个字符),取较大 = 1(下方更长,蓝格是两个依赖)。

看 "a"(str1 第 1 个)和 "a"(str2 第 2 个):相同!这个字符能进 LCS,长度 = 右下角 dp[1][2]=1 再加 1 = 2(紫格,蓝格是它依赖的右下角)。

看 "a" 和 "c":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[1][0]=1(跳过 str1 这个字符),右方 dp[0][1]=2(跳过 str2 这个字符),取较大 = 2(右方更长,蓝格是两个依赖)。

整张表填满。左上角 dp[0][0] = 2,意思是 "abac" 与 "cab" 的最长公共子序列长度为 2(正是 "ab")。LCS 这副骨架有了,下面沿着 dp 表从左上角走一遍,把答案重构出来。

重构规则:站在格子 (i, j),① 若 str1[i]=str2[j],这是公共字符,只写一次,i、j 同时右下移;② 若不同,跟着「LCS 更长」的那一边走,把被跳过那一侧的独有字符先写进答案。指针从 (0,0) 出发。

当前 (0,0):"a" 与 "c" 不同。右方 LCS 2 更大,跟着右方走,要跳过 str2 的 "c",把这个 str2 独有字符先补进答案,只 j++(蓝格往右)。答案现在是 "c"。

当前 (0,1):"a" 两边相同,是公共字符,只写一次 "a" 进答案,然后 i、j 一起往右下走(绿格表示已落定)。答案现在是 "ca"。

当前 (1,2):"b" 两边相同,是公共字符,只写一次 "b" 进答案,然后 i、j 一起往右下走(绿格表示已落定)。答案现在是 "cab"。

指针有一边走到了头(到了 ∅ 边界),剩下另一边的字符不会再有公共部分,原样全部接上即可。这里 str1 还剩 "ac"、str2 还剩 "空",接上后答案 = "cabac"。

复盘:LCS "ab" 是公共骨架只写一次,str2 独有的 "c" 在前面补、str1 独有的 "ac" 在后面补,拼成 "cabac"。验证一下:从它里能跳取出 "abac"(原 str1)和 "cab"(原 str2),且长度 = str1 长 4 + str2 长 3 − LCS 长 2 = 5,无法更短。

边界:相同则原串;无公共则拼接;一方是另一方子序列则取较长串。

两个追问:重构要随机查表所以省不了空间;平手时任选一边都对、固定一个方向即可。

§3

参考代码

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)

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间：O(mn)，m、n 为两串长度。填 dp 表 m×n 个格子各 O(1);重构最多走 m+n 步
空间：O(mn)，需要完整的 dp 二维表参与重构,无法只用滚动数组(重构要回看任意格)

§5

易错点

✗ 错误写法：公共字符写了两次

✓ 正确写法：相同字符重构时只写一次,i、j 同时前进

写两次会让超序列变长、不再最短

✗ 错误写法：不同字符时随便挑一边走

✓ 正确写法：比较 dp[i+1][j] 与 dp[i][j+1],跟更长的 LCS 走

挑错方向会破坏后续公共子序列,结果偏长

✗ 错误写法：忘了接尾巴或丢了 dp 表

✓ 正确写法：结束后把两侧剩余字符接上,且 dp 表全程保留供重构查询

漏接尾巴会缺字符;只存长度还原不出具体答案

面试追问把动画讲成自己的话

追问这题为什么必须保留完整 dp 表,不能像普通 LCS 那样用滚动数组省空间?

普通 LCS 只要长度,一行滚动就够。但本题要还原出具体字符串,重构阶段会从 (0,0) 一路往右下走,每一步都要比较 dp[i+1][j] 与 dp[i][j+1] 来决定方向,这需要随机访问表里任意位置的值。滚动数组只留一行,过去的状态被覆盖了就回不去,所以必须保留 O(mn) 的完整表。

追问当 dp[i+1][j] 等于 dp[i][j+1] 时往哪边走,会影响答案吗?

不影响长度,可能影响具体字符串。两边 LCS 相等说明往任一方向都能得到同样最短的超序列,只是字符排列可能不同。题目通常允许返回任意一个最短解,所以代码里用 dp[i+1][j] ≥ dp[i][j+1] 固定优先走 str1 一侧,保证结果确定即可。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 动态规划套路 106/108

规划兼职工作

LeetCode 1235 · 困难 · 沿着动态规划套路继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

899道动画图解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

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)