主題

LeetCode - 583. Delete Operation for Two Strings 解題心得

Not In My Back Yard | 2021-05-20 00:00:05 | 巴幣 0 | 人氣 35

題目連結:


題目意譯:
給定兩字串 word1 以及 word2,回傳最小所需操作數使得 word1 和 word2 一樣。

每次操作中,你可以刪除其中一個字串中的一個字元。

限制:
1 ≦ word1.length 、 word2.length ≦ 500
word1 和 word2 只由小寫英文字母組成。



範例測資:
範例 1:
輸入: word1 = "sea", word2 = "eat"
輸出: 2
解釋: 你需要一次操作使得 "sea" 變為 "ea",以及另一操作使 "eat" 變為 "ea"。

範例 2:
輸入: word1 = "leetcode", word2 = "etco"
輸出: 4


解題思維:
更加簡化過後的最小編輯距離(Minimum Edit Distance)。

令 D[i][j] 為 word1 (方便起見,這邊的字串索引值從 1 開始數)從索引值 1 到索引值 i 之子字串變為 word2 從索引值 1 到索引值 j 之子字串所需的最少操作數。

原本最小編輯距離的題型會有變換、新增、刪除這三個操作(參見這題),而本題沒有變換,且新增可以視為刪除(字串 A 新增一個字元等價於字串 B 刪除一個字元)。

因此,我們的遞迴式變為以下:
當 word1[i] = word2[j] 時,D[i][j] = D[i - 1][j - 1];

當 word1[i] ≠ word2[j] 時,D[i][j] = min(D[i][j - 1], D[i - 1][j]) + 1。

而初始條件為 D[i][0] = i 、 D[0][j] = j ,對於 i ≧ 1 、 j ≧ 1。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作