付費限定文章

一魚多吃 用DP解 編輯距離 Edit Distance_Leetcode #72 精選75題

Kenny Eliason on Unsplash

題目敘述

給定兩個字串word1和word2，每次操作時，可以有三個選項

1. 插入一個字元
2. 刪除一個字元
3. 替換一個字元

請問把word1轉換成word2的最小操作次數是多少？

題目的原文敘述

約束條件

Constraints:

• 0 <= word1.length, word2.length <= 500

word1, word2 的長度介於 0 ~ 500個字元之間。

請留意，輸入有可能是空字串!

• word1 and word2 consist of lowercase English letters.

word1, word2都只會包含小寫英文字母。

演算法 DP + 字串(字元)比較

題目說每次操作時，可以有三個選項

插入一個字元

刪除一個字元

替換一個字元

DP狀態定義

定義DP(i, j )

= word1[0 ~ i] 和 word2[ 0 ~ j ]的情況下，把word1轉換成word2的最小操作次數

DP狀態轉移關係式, 通則

不失一般性，我們可以從word1 和 word2 的最後一個字元比較，討論會有幾種出現情況。

假設現在的位置位於word1[i], word2[j]

假如 word1[ i ] 等於 word2[ j ]，那麼不需要修改，直接比前面剩下的子字串即可。