1092. Shortest Common Supersequence
思路:
1.先找出str1、str2的最长共同子序列 lcs
2.把lcs从str1、str2去除掉
3.将lcs与str1、str2剩下的字符按照顺序排放就是答案了
假设str1、str2长度分别为n、m
用一个2-D dp矩阵纪录最长共同子序列的长度
从字尾开始找最长共同子序列
这样dp[i][j]就是表示str1[i:]与str2[j:]间最长共同子序列的长度
接着开始组合答案
1.当str1[i] == str2[j] : 把str1[i]放到答案里
2.当str1[i] != str2[j]
(1)dp[i][j+1] > dp[i+1][j] : 把str2[j]放到答案里
(2)dp[i][j+1] <= dp[i+1][j] : 把str1[i]放到答案里
最后把str1、str2剩下的字符全部放到答案就好了
golang code :
func shortestCommonSupersequence(str1 string, str2 string) string {
n, m := len(str1), len(str2)
dp := make([][]int, n+1)
for key := range dp {
dp[key] = make([]int, m+1)
}
for i := n - 1; i > -1; i