1092：最短公共超序列（1976 分）

2019-06-16 约 512 字预计阅读 2 分钟次阅读

力扣第 141 场周赛第 4 题

题目

给你两个字符串 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 都由小写英文字母组成。

相似问题：

分析

典型的 dp，按末尾字符递推即可
由于不仅要最短长度，还要输出对应的子序列，递推时需要保存转移的路径
可以令 rf[i][j]=1/2/3 分别代表 (i,j) 由 (i-1,j)/(i,j-1)/(i-1,j-1) 转移而来，即可反推路径并输出

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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)]
        rf = [[3]*(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] = 1+f[i-1][j-1] 
                elif f[i-1][j]>f[i][j-1]:
                    f[i][j] = f[i-1][j]
                    rf[i][j] = 1
                else:
                    f[i][j] = f[i][j-1]
                    rf[i][j] = 2
        res,i,j = [],m,n
        while i and j:
            st = rf[i][j]
            res.append(str1[i-1] if st&1 else str2[j-1])
            i -= st&1
            j -= st>>1&1
        return str1[:i]+str2[:j]+''.join(res)[::-1]

401 ms

目录

1092：最短公共超序列（1976 分）

题目

分析

解答