力扣每日一题 1092. 最短公共超序列

1. 题目

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

（如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列）

示例

1
2
3
4
5
6

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

提示

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

2. 解题思路

2.1. 动态规划

2.1.1. 状态定义

设dp[i][j]表示字符串str1[:i]和str2[:j]的最短公共超序列，那么dp[i][j]的最后一个字符一定是str1[i-1]或者str2[j-1]中的一个。

2.1.2. 状态转移方程

• 如果str1[i-1] == str2[j-1]，那么dp[i][j] = dp[i-1][j-1] + str1[i-1]
• 如果str1[i-1] != str2[j-1]，那么dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + str1[i-1]或者dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + str2[j-1]

2.1.3. 代码实现

我们在实现代码的时候，一般哦都是从底边开始向上递推，这样可以避免边界问题；然后再关注下边界的情况，注意空间复杂度的优化。

框架代码：

1
2
3
4
5
6
7
8
9

dp[0][0][...] = 边界值
for(状态1 ：所有状态1的值){
    for(状态2 ：所有状态2的值){
        for(...){
          //状态转移方程
          dp[状态1][状态2][...] = 求最值
        }
    }
}

2.2 方案设计

2.2.1 动态规划 + 构造

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

我们根据动态规划方程dp[i][j] 构造出最短公共超序列。

我们使用上述表格来说明如何构造出最短公共超序列。

我们用两个指针$i$和$j$分别指向 str1 和 str2 的末尾，然后我们从后往前遍历：

• 如果str1[i] == str2[j]，那么我们将str1[i]加入到ans中，然后i和j都减一
• 如果str1[i] != str[j]，那么我们就将f[i][j]和f[i-1][j]和f[i][j-1]进行比较
  • 如果f[i][j] == f[i-1][j]，那么我们将str1[i]加入到ans中，然后i减 1
  • 如果f[i][j] == f[i][j-1]，那么我们将str2[j]加入到ans中，然后j减 1

重复上述步骤，直到i或者j为0，然后将剩下的字符串加入到ans中。

Python代码实现：

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
32
33

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m = len(str1)
        n = 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])

2.2.2 复杂度分析

• 时间复杂度：$O(mn)$
• 空间复杂度：$O(mn)$

3. 总结

• 动态规划问题一般都是求最值问题，状态转移方程也是求最值问题，那么就要想清楚如何求最值
• 本题中，最后一个字符一定是str1[i-1]或者str2[j-1]中的一个，那么就要想清楚如何求最值

4. 引用

题目来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shortest-common-supersequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。