主題

LeetCode - 72. Edit Distance 解題心得

Not In My Back Yard | 2021-06-13 00:00:03 | 巴幣 0 | 人氣 17

題目連結:


題目意譯:
給定兩個字串 word1 和 word2 ,回傳將 word1 轉變為 word2 所需要的最小操作數。

你有以下三種操作可以套用在字詞上:
插入一個字元
刪除一個字元
替換一個字元

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



範例測資:
範例 1:
輸入: word1 = "horse", word2 = "ros"
輸出: 3
解釋:
horse → rorse (將 'h' 替換為 'r')
rorse → rose (移除 'r')
rose → ros (移除 'e')

範例 2:
輸入: word1 = "intention", word2 = "execution"
輸出: 5
解釋:
intention → inention (移除 't')
inention → enention (將 'i' 替換為 'e')
enention → exention (將 'n' 替換為 'x')
exention → exection (將 'n' 替換為 'c')
exection → execution (插入 'u')


解題思維:
最小編輯距離(Minimum Edit Distance)的題型,參見這題




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

創作回應

更多創作