給你兩個單詞 word1 和 word2，請你計算出將 word1 轉換成 word2 所使用的最少操作數 。
你可以對一個單詞進行如下三種操作：
1.插入一個字符2.刪除一個字符3.替換一個字符
示例 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')來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/edit-distance
Link：https://leetcode.com/problems/edit-distance/
動態規劃O(M*N)
'' R O S # word2
'' 0 1 2 3
H 1 > 插入 | \O 2 | \ | \ R 3 | \ | \ S 4 | \ | \ 替換E 5 v 刪除 45.Degree
# word1遞推公式定義table[i][j]代表word1[:i]與word2[:j]能夠匹配的時候需要的操作次數(包含i, j)
# 如果兩個單詞字符word1[i] == word2[j]:table[i][j] = table[i - 1][j - 1]
# 如果不想等, 三個策略選擇次數最少的一個方案:
# 策略1, word1插入一個字符
table[i][j] = table[i][j - 1] + 1
# 策略2, word1刪除一個字符
table[i][j] = table[i - 1][j] + 1
# 策略3, word1替換一個字符
table[i][j] = table[i - 1][j - 1]
計算方向水平逐行掃描
邊界條件# 水平第一行, 代表空字符的word1, 與word2相比配, 只能依次插入
# 水平第一行, 代表word1, 與空字符的word2相比配, 只能依次刪除
初始條件table[0][0] = 0 # 表示兩個空字符，無需任何操作代碼如下:
class Solution: def minDistance(self, word1: str, word2: str) -> int:
table = [[0 for j in range(len(word2) + 1)] for i in range(len(word1) + 1)]
for j in range(1, len(table[0])): table[0][j] = table[0][j - 1] + 1
for i in range(1, len(table)): table[i][0] = table[i - 1][0] + 1
for i in range(len(word1)): for j in range(len(word2)):
if word1[i] == word2[j]: table[i + 1][j + 1] = table[i][j] else: table[i + 1][j + 1] = min(table[i + 1][j], table[i][j + 1], table[i][j]) + 1
return table[-1][-1]手動遞推'' R O S # word2
'' 0 1 2 3
H 1 1 2 3
O 2 2 1 2
R 3 2 2 2
S 4 3 3 2
E 5 4 4 3
# word1--End--