What is the shortest common supersequence problem?

It is the task of finding the minimal-length string containing two given strings as subsequences, preserving relative order.

How does dynamic programming apply to this problem?

We use state transition DP to compute the longest common subsequence, which guides the shortest supersequence construction.

Can multiple valid shortest common supersequences exist?

Yes, when multiple sequences share the same minimal length, any of them is acceptable as a solution.

What are common mistakes when solving Shortest Common Supersequence?

Failing to use LCS first, merging characters incorrectly, or not handling remaining characters at the end can produce invalid or longer results.

Is there a space optimization for this DP approach?

Yes, instead of storing the full dp table, two rows can be maintained to reduce space from O(n*m) to O(min(n,m)).

#1092

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最短公共超序列

给你两个字符串 str1 和 str2 ，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。如果从字符串 t 中删除一些字符（也可能不删除），可以得到字符串 s ，那么 s 就是 t 的一个子序列。示例 1：输入： str1…

字符串动态规划

题目描述

给你两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个，则可以返回满足条件的 任意一个 答案。

如果从字符串 t 中删除一些字符（也可能不删除），可以得到字符串 s ，那么 s 就是 t 的一个子序列。

示例 1：

输入：str1 = "abac", str2 = "cab"
输出："cabac"
解释：
str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。 
str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。
最终我们给出的答案是满足上述属性的最短字符串。

示例 2：

输入：str1 = "aaaaaaaa", str2 = "aaaaaaaa"
输出："aaaaaaaa"

提示：

1 <= str1.length, str2.length <= 1000
str1 和 str2 都由小写英文字母组成。

lightbulb

解题思路

方法一：动态规划 + 构造

我们先用动态规划求出两个字符串的最长公共子序列，然后根据最长公共子序列构造出最短公共超序列。

定义 $f[i][j]$ 表示字符串 $str1$ 的前 $i$ 个字符和字符串 $str2$ 的前 $j$ 个字符的最长公共子序列的长度。状态转移方程如下：

f[i][j] = \begin{cases} 0 & i = 0 \textit{ or } j = 0 \\ f[i - 1][j - 1] + 1 & str1[i - 1] = str2[j - 1] \\ \max(f[i - 1][j], f[i][j - 1]) & str1[i - 1] \neq str2[j - 1] \end{cases}

接下来我们基于 $f[i][j]$ 构造出最短公共超序列。

str1:       a   b   a   c

str2:   c   a   b

ans:    c   a   b   a   c

不妨对照着上面的示例字符串，来看看如何构造出最短公共超序列。

我们用双指针 $i$ 和 $j$ 分别指向字符串 $str1$ 和 $str2$ 的末尾，然后从后往前遍历，每次比较 $str1[i]$ 和 $str2[j]$ 的值：

如果 $str1[i] = str2[j]$ ，则将 $str1[i]$ 或 $str2[j]$ 中的任意一个字符加入到最答案序列的末尾，然后 $i$ 和 $j$ 同时减 $1$ ；
如果 $str1[i] \neq str2[j]$ $s t r 1 [i] \neq = s t r 2 [j]$ ，则将 $f[i][j]$ $f [i] [j]$ 与 $f[i - 1][j]$ $f [i - 1] [j]$ 和 $f[i][j - 1]$ $f [i] [j - 1]$ 中的最大值进行比较：
- 如果 $f[i][j] = f[i - 1][j]$ ，则将 $str1[i]$ 加入到答案序列的末尾，然后 $i$ 减 $1$ ；
- 如果 $f[i][j] = f[i][j - 1]$ ，则将 $str2[j]$ 加入到答案序列的末尾，然后 $j$ 减 $1$ 。

重复上述操作，直到 $i = 0$ 或 $j = 0$ ，然后将剩余的字符串加入到答案序列的末尾即可。

最后我们将答案序列反转，即可得到最终的答案。

时间复杂度 $O(m\times n)$ ，空间复杂度 $O(m\times n)$ 。其中 $m$ 和 $n$ 分别是字符串 $str1$ 和 $str2$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

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

speed

复杂度分析

指标	值
时间	complexity is O(n * m) due to filling the LCS dp table for all pairs of indices. Space complexity is also O(n * m) for storing the dp table. Optimizations like using two rows instead of full dp can reduce space to O(min(n, m)).
空间	O(n \cdot m)

psychology

面试官常问的追问

外企场景

question_mark
Candidate recognizes dynamic programming structure for subsequences.
question_mark
Candidate efficiently computes LCS before merging strings.
question_mark
Candidate handles edge cases where one string is entirely a subsequence of the other.

warning

常见陷阱

外企场景

error
Not using LCS leads to longer than necessary supersequence.
error
Incorrectly merging characters may violate subsequence property.
error
Failing to append remaining unmatched characters at the end of reconstruction.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return all possible shortest common supersequences.
arrow_right_alt
Compute shortest common supersequence for more than two strings.
arrow_right_alt
Modify problem to find supersequence minimizing a custom cost function.

help

常见问题

外企场景

继续练习

#1048 最长字符串链 #1143 最长公共子序列 #1147 段式回文