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