难度: Hard
给你两个字符串 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 <= 1000str1 和 str2 都由小写英文字母组成。运行时间: 324 ms
内存: 391.9 MB
class Solution:
def shortestCommonSupersequence(self, s1: str, s2: str) -> str:
# 匹配最长子序列
l1,l2 = len(s1),len(s2)
dp = [[""] * (l2 + 1) for _ in range(l1 + 1)]
for i in range(l1 - 1, -1,-1):
for j in range(l2 - 1,-1,-1):
if s1[i] == s2[j]:
dp[i][j] = s1[i]+ dp[i + 1][j + 1]
else:
if len(dp[i + 1][j]) >= len(dp[i][j + 1]):
dp[i][j] = dp[i + 1][j]
else:
dp[i][j] = dp[i][j + 1]
print(dp[0][0])
s = dp[0][0]
# s = "ab"
ans = ''
i,j,k = 0,0,0
while i < l1 and j < l2 and k < len(s):
if s[k] == s1[i] and s[k] == s2[j]:
ans += s[k]
i+=1
j+=1
k+=1
continue
if s[k] != s1[i]:
ans += s1[i]
i+=1
if s[k] != s2[j]:
ans += s2[j]
j += 1
while i < l1:
ans += s1[i]
i+=1
while j < l2:
ans += s2[j]
j+=1
return ans
此题解采用动态规划先找出两个字符串的最长公共子序列(LCS)，然后构建最短公共超序列(SCS)。首先，使用一个二维数组dp，其中dp[i][j]存储s1的前i个字符和s2的前j个字符的LCS。遍历两个字符串，填充dp数组。接着，根据dp数组的内容，从头到尾构建出SCS。在构建SCS的过程中，如果当前字符属于LCS，则添加这个字符到结果中，同时移动两个字符串的指针；如果不是，则分别添加两个字符串的当前字符，直到处理完所有字符。
时间复杂度: O(l1 * l2)
空间复杂度: O(l1 * l2)
class Solution:
def shortestCommonSupersequence(self, s1: str, s2: str) -> str:
# 初始化长度
l1, l2 = len(s1), len(s2)
# 创建动态规划表
dp = [[''] * (l2 + 1) for _ in range(l1 + 1)]
# 填充dp表，计算LCS
for i in range(l1 - 1, -1, -1):
for j in range(l2 - 1, -1, -1):
if s1[i] == s2[j]:
dp[i][j] = s1[i] + dp[i + 1][j + 1]
else:
dp[i][j] = dp[i + 1][j] if len(dp[i + 1][j]) >= len(dp[i][j + 1]) else dp[i][j + 1]
# 构建最短公共超序列
ans = ''
i, j, k = 0, 0, 0
while i < l1 and j < l2 and k < len(dp[0][0]):
if s1[i] == dp[0][0][k] and s2[j] == dp[0][0][k]:
ans += dp[0][0][k]
i += 1
j += 1
k += 1
else:
if s1[i] != dp[0][0][k]:
ans += s1[i]
i += 1
if s2[j] != dp[0][0][k]:
ans += s2[j]
j += 1
# 添加剩余的字符
ans += s1[i:]
ans += s2[j:]
return ans
dp数组的维度是根据两个输入字符串s1和s2的长度来确定的。具体来说，如果s1长度为l1，s2长度为l2，则dp数组的维度为(l1+1)x(l2+1)。这样的维度选择可以保证dp[i][j]能够表示s1的前i个字符和s2的前j个字符的最长公共子序列。使用二维数组是因为这样可以方便地通过下标来访问和更新两个字符串的任意位置的LCS长度，同时便于实现二维动态规划算法。
根据题解的方法，当当前字符不属于LCS时，确实会同时添加两个字符串的当前字符。这种做法可能会导致结果不是最短的公共超序列，因为它可能同时添加两个不同的字符，而不是选择其中一个字符来保持序列尽可能短。为了保证得到真正的最短公共超序列，应当在添加字符时更加谨慎地考虑哪个字符能够最有效地推进序列构建，而不是简单地同时添加两者。
在计算LCS时，从后向前遍历字符串可以更方便地利用后面已经计算好的结果来更新当前的dp值。这是因为每个dp[i][j]的值依赖于dp[i+1][j]、dp[i][j+1]和dp[i+1][j+1]的值。如果从后向前遍历，这些依赖的值在更新当前dp[i][j]时已经计算完毕，无需额外的存储空间来保存中间结果。这种方式可以减少计算中的冗余并优化空间使用。
在构建最短公共超序列的过程中，如果在完成LCS的字符添加后，某个或两个字符串还有剩余字符，则需要将这些剩余字符直接添加到结果字符串的末尾。这是因为这些剩余字符并没有在另一个字符串中找到对应的匹配，但它们是构成超序列的必要部分。添加剩余字符的顺序应当与原字符串中的顺序保持一致，以确保结果是正确的超序列。