最小編輯代價
問題描述
給你兩個單詞 word1 和 word2，請你計算出將 word1 轉換成 word2 所使用的最少操作數 。你可以對一個單詞進行如下三種操作：
- 插入一個字元
- 刪除一個字元
- 替換一個字元
示例：
輸入：word1 = “horse”, word2 = “ros”
輸出：3
解釋：
horse -> rorse (將 'h' 替換為 'r')
rorse -> rose (刪除 'r')
rose -> ros (刪除 'e')
分析問題
根據題目要求，你可以對任意一個單詞進行增、刪、改三種操作，題目給定兩個單詞，所以一共有2*3=6中操作。但是這裡包含了一些重複的情況，假設給定的單詞是A和B。
- 對單詞A刪除一個字元和對單詞B增加一個字元是等價的。比如單詞A是「abc」，單詞B為「bc」時，我們既可以刪除單詞A的第一個字元a，得到相同的「bc」，也可以在單詞B的開頭添加一個字元a，得到相同的「abc」。
- 同理，對單詞B刪除一個字元和對單詞A插入一個字元也是等價的。
- 對單詞A替換一個字元和對單詞B替換一個字元也是等價的。
所以本質上不同的操作只有三種，即
- 在單詞A中插入一個字元
- 在單詞A中刪除一個字元
- 修改單詞A中的一個字元
這樣我們可以把原問題拆分成若干個子問題，我們假設A=”horse”，B=”ros”。下面來看一下如何具體操作。
- 在單詞A中插入一個字元：如果我們知道「horse」到「ro」的編輯距離為a，那麼「horse」到「ros」的編輯距離不會超過a+1。因為我們只需要在「horse」的末尾添加一個字元s即可。
- 在單詞A中刪除一個字元：如果我們知道「hors」 到 「ros」的編輯距離為b，那麼「horse」到 「ros」的編輯距離不會超過 b + 1。因為我們只需要刪除「horse」的最後一個字元e即可。
- 修改單詞A中的一個字元：如果我們知道「hors」到「ro」的編輯距離為c，那麼「horse」到 「ros」的編輯距離不會超過 c + 1。因為我們只需要把「horse」的最後一個字元e修改為s即可。
那麼從「horse」變成「ros」的最小編輯距離為min(a+1,b+1,c+1)。
所以這道題就可以使用動態規劃的方式來求解。我們假設dp[i] [j] 表示word1的前i個字元，變換到word2的前j個字元的最小編輯距離。根據上面的分析，我們可以知道它是由以下三種狀態轉移的最小值過來的。即
- dp[i] [j] = dp[i] [j-1] +1，即在單詞A中增加一個字元
- dp[i] [j] = dp [i-1] [j] + 1，即在單詞A中刪除一個字元
- dp[i] [j] = dp[i-1] [j-1] +1，即在單詞A中替換一個字元
所以動態轉移方程為：
若A、B的最後一個字元相同 **dp[i] [j] = min(dp[i] [j-1]+1，dp [i-1] [j]+1，dp[i-1] [j-1]) **。
若A、B的最後一個字元不相同 dp[i] [j] = min(dp[i] [j-1]+1，dp [i-1] [j]+1，dp[i-1] [j-1]+1)。
下面我們來看一下邊界情況，一個空串和一個非空串的編輯距離dp[i] [0] = i, dp[0] [j] =j。dp[i] [0] 相當於對word1執行了i次刪除操作，dp[0] [j]相當於對word1進行了j次插入操作。
下面我們來看一下程式碼實現。
class Solution:
def minDistance(self, word1, word2):
#求出單詞的長度
n = len(word1)
m = len(word2)
#判斷是否是空串
if n==0:
return m
if m==0:
return n
#定義狀態轉移矩陣
dp = [[0] * (m + 1) for _ in range(n + 1)]
#處理邊界條件
for i in range(n + 1):
dp[i][0] = i
for j in range(m + 1):
dp[0][j] = j
#填充狀態轉移矩陣
for i in range(1, n + 1):
for j in range(1, m + 1):
#上邊狀態轉移過來
up = dp[i - 1][j] + 1
#左邊狀態轉移過來
left = dp[i][j - 1] + 1
#左上的狀態
left_up = dp[i - 1][j - 1]
#如果最後一個字元不相同，left_up需要加1
if word1[i - 1] != word2[j - 1]:
left_up += 1
dp[i][j] = min(left, up, left_up)
return dp[n][m]
該演算法的時間複雜度和空間複雜度都是O(n*m)。
最後
送大家幾本比較不錯的演算法書籍~
小爭哥數據結構與演算法
鏈接://pan.baidu.com/s/19Jk_G_-QTnGb3GRyzbENgA
密碼:keis
Google大佬LeetCode刷題指南
鏈接://pan.baidu.com/s/1vtRIsVltTxmIioqqkeSS5g
密碼:r3xg
演算法小抄
鏈接://pan.baidu.com/s/1rU_T6GRZ-WmV9QFmnJfCBg
密碼:unh5
