1 題目描述

給定兩個單詞word1和word2，找到將word1轉換為word2所需的最小操作數。

操作包括插入一個字符、刪除一個字符、替換一個字符
美的操作的成本是1

2 解法

我會建議先畫出一個dp圖，這個dp代表，word1的前i個字元與word2的前j個字元的最小操作數，這樣就可以從dp[i-1][j-1]推導出dp[i][j]。
你會發現，第一列或是第一排，也就是word1或word2為空的時候，最小操作數就是當前字元的長度，可以透過這個特性來初始化dp。

如上圖所示，可以寫出以下程式碼進行初始化：

class Solution:
    def minDistance(self, w1: str, w2: str) -> int:
        m = len(w2)
        n = len(w1)

        # 如果某一方為空，但是雙方長度不一樣，就回傳最長的那個
        if (n == 0 or m == 0) and n != m:
            return max(m, n)

        # 初始化dp
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

        # 初始化第一行與第一列
        for i in range(m+1):
            dp[i][0] = i
        for j in range(n+1):
            dp[0][j] = j

接下來，我們先來使用一個比較簡單的例子來說明一下會有哪些狀況：

當word1[i] == word2[j]時，不需要進行任何操作，繼續往下一個字元比較即可
- (i+1,j+1) 這會對應到 dp[i][j] = dp[i-1][j-1]
當word1[i] != word2[j]時，有三種操作方式：
- 插入：(i,j+1) 這會對應到 dp[i][j-1] + 1
- 刪除：(i+1,j) 這會對應到 dp[i-1][j] + 1
- 替換：(i+1,j+1) 這會對應到 dp[i-1][j-1] + 1

我來說明為什麼會這樣對應：
情境1:當比較的字元相同時

從上圖你會發現，如果我們求dp[3][5]時，因為word1[3-1] == word2[5-1] == "s"，所以我們看能有三種操作方式，但是上面的操作方式中，只有從斜方向來的成本最小，因為當下比較的字元是相同的，所以我們不需要進行任何操作，可以直接取dp[2][4]的值。如果我們硬要取上面或是左邊的值，那就會多一次操作。

情境2:當比較的字元不同時

從上圖如果我們求dp[3][4]時，因為word1[3-1] != word2[4-1]，所以我們看能有三種操作方式，上面三種操作方式中我們要取最小的。從這個例子裡面，斜角或是左邊的值是最小的。

共通點
然後你會發現這三個操作的公式如下：

上面（插入）：dp[i][j-1] + 1
左邊（刪除）：dp[i-1][j] + 1
斜角（替換）：dp[i-1][j-1] + 1（當前字元不同）或 dp[i-1][j-1]（當前字元相同）

這樣我們就可以寫出以下程式碼：

class Solution:
    def minDistance(self, w1: str, w2: str) -> int:
        m = len(w2)
        n = len(w1)
        if (n == 0 or m == 0) and n != m:
            return max(m, n)
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(m+1):
            dp[i][0] = i
        for j in range(n+1):
            dp[0][j] = j

        # 開始填表，因為第一行與第一列已經初始化了，所以從1開始
        for i in range(1, m+1):
            for j in range(1, n+1):
                # 計算top(插入)、left(刪除)、dia(替換)的成本
                top = dp[i-1][j]
                dia = dp[i-1][j-1]
                left = dp[i][j-1]
                # 如果當前字元不同，就取最小的並且+1操作
                if w2[i-1] != w1[j-1]:
                    dp[i][j] = 1 + min(top, dia, left)
                # 如果當前字元相同，就取斜角的值（因為不需要操作成本）
                else:
                    dp[i][j] = dia

        # 回傳最後一個值
        return dp[m][n]