1092. 最短公共超序列

Difficulty
Hard
Tags
动态规划
URL
https://leetcode-cn.com/problems/shortest-common-supersequence/
Star
❤
给出两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。
（如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列）
示例：
输入：str1 = "abac", str2 = "cab"
输出："cabac"
解释：
str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。
str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。
最终我们给出的答案是满足上述属性的最短字符串。
提示：
  1. 1 <= str1.length, str2.length <= 1000
  1. str1 和 str2 都由小写英文字母组成。

法1 动态规划

思路
本题是要求返回最短超序列，而不是返回最短超序列的长度。那么先看问题：最短公共超序列长度。
显然为双序列类型题目，按照套路：
  1. 定义状态：dp[i][j] ⇒ 序列s[0:i] 和序列t[0:j]的最短公共超序列长度
  1. 状态转移：外面两层大循环遍历i和j；核心从s[i]与t[j]的关系作为突破口，拼命往dp[i-1][j-1], dp[i][j-1], dp[i-1][j]转移。
      • 如果s[i] == t[j] 那么当前状态dp[i][j]就等于 s[0:i-1]和t[0:j-1]的最长公共子序列的长度加一，即dp[i][j] = dp[i-1][j-1]
      • 如果s[i] ≠ t[j] 那么当前状态就等于 s[0:i-1]和t[0:j]的最长公共子序列 与 s[0:i]和t[0:j-1]的最短公共超序列 较小值加一。即dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + 1
  1. 初始化。对于dp[i][0] 和dp[0][j] 表示空序列与另外一个非空序列的超序列最小长度，那么应该是非空空序列的长度
代码如下：
class Solution:
    def shortestCommonSupersequence(self, text1: str, text2: str) -> int:
        dp = [[0]*(len(text2)+1) for _ in range(len(text1)+1)]
				
				# 初始化
				for i in range(0, len(dp)):
						dp[i][0] = i
				for j in range(0, len(dp[0])):
						dp[0][j] = j

        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1

        return dp[-1][-1]
然鹅，本体要求的是最短公共超序列本身，即要返回的不是长度，而是超序列。所以状态的定义要发生变化，但是状态转移的大体逻辑依旧相似。
状态定义 ： dp[i][j] 为 序列s[0:i] 和序列t[0:j]的最短公共超序列
状态转移：判断s[0:i-1] 和序列t[0:j]的最短公共超序列 与 s[0:i] 和序列t[0:j-1]的最短公共超序列 的长度大小， 选择较小的一方再将当前元素加进去。
题解 
class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        dp = [["" for _ in range(len(str2)+1)] for _ in range(len(str1)+1)]     
        # 初始化
        for i in range(1, len(dp)):
            dp[i][0] = str1[0:i]
        for j in range(1, len(dp[0])):
            dp[0][j] = str2[0:j]
        # 状态转移
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + str1[i-1]
                else:
                    if len(dp[i-1][j]) < len(dp[i][j-1]):
                        dp[i][j] = dp[i-1][j] + str1[i-1]
                    else:
                        dp[i][j] = dp[i][j-1] + str2[j-1]

        return dp[-1][-1]

法2 动态规划 + 回溯

思路
先用动态规划计算出最短公共超序列的长度。然后根据dp数组回溯，一步一步往回走，推出结果。
为什么可以倒退出来呢？因为dp数组是不对称的：
  • 如果str1[i] == str2[j], 那么说明此时添加 str1[i] 或者str2[j]到结果中
  • 如果dp[i][j] = dp[i-1][j] + 1，说明此时添加到结果的是str1[i]
  • 如果dp[i][j] = dp[i][j-1] + 1, 说明此时添加到结果的是str2[j]
💡
核心思想：根据dp的取值变化，可以推断出当时采取了什么操作，是将str1[i]加到结果上了，还是将str2[j]加上来了。 建立dp的过程是不对称的，所以可以推断出来
notion imagenotion image
题解
class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        if len(str1) == 0 or len(str2) == 0:
            return str1 if str1 else str2

        str1 = "#" + str1
        str2 = "#" + str2

        dp = [[0] * len(str2) for _ in range(len(str1))]
        # 初始化
        for i in range(1, len(str1)):
            dp[i][0] = i
        for j in range(1, len(str2)):
            dp[0][j] = j
        # 动态规划，计算每一步的最短超序列长度
        for i in range(1, len(str1)):
            for j in range(1, len(str2)):
                if str1[i] == str2[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
        
        print(dp)
        # 根据dp数组反推 路径（结果）
        res = ""
        i = len(str1) - 1
        j = len(str2) - 1
        while i >= 0 and j >= 0:
						# 通过这行代码 可以查看路径
            print(i, j, res)
            if str1[i] == str2[j]:
                res = str1[i] + res
                i -= 1
                j -= 1
            elif dp[i][j] == dp[i-1][j] + 1:
                res = str1[i] + res
                i -= 1
            elif dp[i][j] == dp[i][j-1] + 1:
                res = str2[j] + res
                j -= 1
	       # 因为最后 当 i=0,j=0时候， str1[0] == str2[0]m此肯定会将"#" 加进去，所以需要去掉
        return res[1:]