推 oin1104: 卷什麼 我都回台北爽了 03/01 22:19
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-- {
for j := m - 1; j > -1; j-- {
if str1[i] == str2[j] {
dp[i][j] = dp[i+1][j+1] + 1
} else {
dp[i][j] = max(dp[i+1][j], dp[i][j+1])
}
}
}
ans, idx1, idx2 := strings.Builder{}, 0, 0
for idx1 < n && idx2 < m {
if str1[idx1] == str2[idx2] {
ans.WriteByte(str1[idx1])
idx1++
idx2++
} else if dp[idx1][idx2+1] > dp[idx1+1][idx2] {
ans.WriteByte(str2[idx2])
idx2++
} else {
ans.WriteByte(str1[idx1])
idx1++
}
}
ans.WriteString(str1[idx1:])
ans.WriteString(str2[idx2:])
return ans.String()
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.143.172 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1740838159.A.5D9.html