題目描述：

給你兩個(gè)單詞 word1 和 word2， 請(qǐng)返回將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。

你可以對(duì)一個(gè)單詞進(jìn)行如下三種操作：

插入一個(gè)字符
刪除一個(gè)字符
替換一個(gè)字符

示例 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’)

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小寫(xiě)英文字母組成

此題的解題思路與LeetCode-1143. 最長(zhǎng)公共子序列【字符串 動(dòng)態(tài)規(guī)劃】非常一致！

解題思路一：動(dòng)規(guī)五部曲

1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義
   dp[i][j] 表示以下標(biāo)i-1為結(jié)尾的字符串word1，和以下標(biāo)j-1為結(jié)尾的字符串word2，最近編輯距離為dp[i][j]。

有同學(xué)問(wèn)了，為啥要表示下標(biāo)i-1為結(jié)尾的字符串呢，為啥不表示下標(biāo)i為結(jié)尾的字符串呢？

為什么這么定義我在 718. 最長(zhǎng)重復(fù)子數(shù)組 (opens new window)中做了詳細(xì)的講解。

其實(shí)用i來(lái)表示也可以！ 用i-1就是為了方便后面dp數(shù)組初始化的。

2. 確定遞推公式
   在確定遞推公式的時(shí)候，首先要考慮清楚編輯的幾種操作，整理如下：

if (word1[i - 1] == word2[j - 1])不操作
if (word1[i - 1] != word2[j - 1])增刪換

也就是如上4種情況。

if (word1[i - 1] == word2[j - 1]) 那么說(shuō)明不用任何編輯，dp[i][j] 就應(yīng)該是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];

此時(shí)可能有同學(xué)有點(diǎn)不明白，為啥要即dp[i][j] = dp[i - 1][j - 1]呢？

那么就在回顧上面講過(guò)的dp[i][j]的定義，word1[i - 1] 與 word2[j - 1]相等了，那么就不用編輯了，以下標(biāo)i-2為結(jié)尾的字符串word1和以下標(biāo)j-2為結(jié)尾的字符串word2的最近編輯距離dp[i - 1][j - 1]就是 dp[i][j]了。

在下面的講解中，如果哪里看不懂，就回想一下dp[i][j]的定義，就明白了。

在整個(gè)動(dòng)規(guī)的過(guò)程中，最為關(guān)鍵就是正確理解dp[i][j]的定義！

if (word1[i - 1] != word2[j - 1])，此時(shí)就需要編輯了，如何編輯呢？

操作一：word1刪除一個(gè)元素，那么就是以下標(biāo)i - 2為結(jié)尾的word1 與 j-1為結(jié)尾的word2的最近編輯距離 再加上一個(gè)操作。
即 dp[i][j] = dp[i - 1][j] + 1;

操作二：word2刪除一個(gè)元素，那么就是以下標(biāo)i - 1為結(jié)尾的word1 與 j-2為結(jié)尾的word2的最近編輯距離 再加上一個(gè)操作。
即 dp[i][j] = dp[i][j - 1] + 1;

這里有同學(xué)發(fā)現(xiàn)了，怎么都是刪除元素，添加元素去哪了。

word2添加一個(gè)元素，相當(dāng)于word1刪除一個(gè)元素，例如 word1 = “ad” ，word2 = “a”，word1刪除元素’d’ 和 word2添加一個(gè)元素’d’，變成word1=“a”, word2=“ad”， 最終的操作數(shù)是一樣！ dp數(shù)組如下圖所示意的：

            a                         a     d+-----+-----+             +-----+-----+-----+|  0  |  1  |             |  0  |  1  |  2  |+-----+-----+   ===>      +-----+-----+-----+a |  1  |  0  |           a |  1  |  0  |  1  |+-----+-----+             +-----+-----+-----+d |  2  |  1  |+-----+-----+

操作三：替換元素，word1替換word1[i - 1]，使其與word2[j - 1]相同，此時(shí)不用增刪加元素。

可以回顧一下，if (word1[i - 1] == word2[j - 1])的時(shí)候我們的操作 是 dp[i][j] = dp[i - 1][j - 1] 對(duì)吧。

那么只需要一次替換的操作，就可以讓 word1[i - 1] 和 word2[j - 1] 相同。

所以 dp[i][j] = dp[i - 1][j - 1] + 1;

綜上，當(dāng) if (word1[i - 1] != word2[j - 1]) 時(shí)取最小的，即：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

遞歸公式代碼如下：

if (word1[i - 1] == word2[j - 1]) {dp[i][j] = dp[i - 1][j - 1];
}
else {dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}

3. dp數(shù)組如何初始化
   再回顧一下dp[i][j]的定義：

dp[i][j] 表示以下標(biāo)i-1為結(jié)尾的字符串word1，和以下標(biāo)j-1為結(jié)尾的字符串word2，最近編輯距離為dp[i][j]。

那么dp[i][0] 和 dp[0][j] 表示什么呢？

dp[i][0] ：以下標(biāo)i-1為結(jié)尾的字符串word1，和空字符串word2，最近編輯距離為dp[i][0]。

那么dp[i][0]就應(yīng)該是i，對(duì)word1里的元素全部做刪除操作，即：dp[i][0] = i;

同理dp[0][j] = j;

4. 確定遍歷順序
   從如下四個(gè)遞推公式：

dp[i][j] = dp[i - 1][j - 1]
dp[i][j] = dp[i - 1][j - 1] + 1
dp[i][j] = dp[i][j - 1] + 1
dp[i][j] = dp[i - 1][j] + 1
可以看出dp[i][j]是依賴(lài)左方，上方和左上方元素的，如圖：

所以在dp矩陣中一定是從左到右從上到下去遍歷。

5. 舉例推導(dǎo)dp數(shù)組
   以示例1為例，輸入：word1 = “horse”, word2 = "ros"為例，dp矩陣狀態(tài)圖如下：
   

class Solution:def minDistance(self, word1: str, word2: str) -> int:dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)]for i in range(len(word1)+1):dp[i][0] = ifor j in range(len(word2)+1):dp[0][j] = jfor i in range(1, len(word1)+1):for j in range(1, len(word2)+1):if word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1]else:dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1return dp[-1][-1]

時(shí)間復(fù)雜度：O(nm)
空間復(fù)雜度：O(nm)

解題思路二：動(dòng)態(tài)規(guī)劃【版本二】

class Solution:def minDistance(self, word1: str, word2: str) -> int:m, n = len(word1), len(word2)dp = [[0] * (n+1) for _ in range(m+1)]for i in range(m+1):dp[i][0] = ifor j in range(n+1):dp[0][j] = jfor i in range(1, m+1):for j in range(1, n+1):if word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1]else:dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1return dp[-1][-1]

時(shí)間復(fù)雜度：O(nm)
空間復(fù)雜度：O(nm)

解題思路三：0

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)