72. Edit Distance

──────────────────────────────────────────────────────────────────────

72. Edit Distance

給兩個字串 word1 和 word2，每次可以插入、刪除或替換一個字元，問把 word1 變成 word2 最少要幾次操作。

這一題是真的很難的一道題目，難不是難在怎麼寫，是難在這個最短編輯距離的方式是：俄羅斯科學家弗拉基米爾·萊文斯坦在1965年提出的概念。又稱萊文斯坦距離（Levenshtein distance）。

理解原理後實作並不難，但是要直接看到題目想到要用動態規劃寫，超難！基本上如果有公司面試這個問題，我會直接放棄。

思路

狀態就是兩個指針

兩個字串互相比對的題目，狀態幾乎都是「兩邊各看到哪裡」。所以定義：

dp(i, j) = 把 word1[i:] 變成 word2[j:] 最少要幾次操作

答案就是 dp(0, 0)。

字元相同不用花錢

如果 word1[i] == word2[j]，這一位什麼都不用做，兩個指針同時往前，而且不加 1：

word1 = "rose"     word2 = "ros"
         ^                  ^
         r == r  -> 兩邊同時往前，不花操作

word1 = "horse"     word2 = "ros"
         ^                   ^
         h != r  -> 一定要花一次操作

三種操作就是三種指針移動

這是整題唯一難的地方 —— 把「插入／刪除／替換」翻譯成指針怎麼動：

操作	對 `word1` 做了什麼	指針	剩下要解的子問題
刪除	刪掉 `word1[i]`	`i + 1`、`j` 不動	`dp(i + 1, j)`
插入	在 `word1` 插入 `word2[j]`	`j + 1`、`i` 不動	`dp(i, j + 1)`
替換	把 `word1[i]` 換成 `word2[j]`	兩個都 `+1`	`dp(i + 1, j + 1)`

插入那一列最容易卡住：程式裡並沒有真的去改字串，而是「假裝插了一個 word2[j]」—— 既然插進去的字就等於 word2[j]，那一位當場就配對掉了，所以是 j 往前而 i 留在原地。刪除則相反，word1[i] 被丟掉，word2[j] 還沒被服務到。

三種都要花一次操作，所以取最小值之後 + 1：

d p (i, j) = {\begin{matrix} d p (i + 1, j + 1) & if w o r d 1 [i] = w o r d 2 [j] \\ 1 + \min (d p (i + 1, j), d p (i, j + 1), d p (i + 1, j + 1)) & otherwise \end{matrix}

邊界：一邊走完就沒得選了

i 到底 —— word1 沒字了，word2 還剩 len(word2) - j 個字，只能全部插入
j 到底 —— word2 沒字了，word1 還剩 len(word1) - i 個字，只能全部刪掉

兩邊都到底就是 0。剩幾個字就要花幾次操作，沒有更省的走法。

解題方向

自頂向下

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        
        @cache
        def dp(i, j):
            if i == len(word1) and j == len(word2):
                return 0
            if i == len(word1):
                return len(word2) - j
            if j == len(word2):
                return len(word1) - i
            if word1[i] == word2[j]:
                return dp(i + 1, j + 1)
            return min(
                dp(i + 1, j),
                dp(i, j + 1),
                dp(i + 1, j + 1)
            ) + 1
        
        return dp(0, 0)

min 裡面那三行的順序，就是上面表格的刪除、插入、替換。

自底向上

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        rows = len(word1)
        cols = len(word2)
        if rows == 0 or cols == 0:
            return rows + cols

        memo = [[0] * (cols+1) for _ in range(rows+1)]

        for i in range(rows+1):
            memo[i][0] = i

        for j in range(cols+1):
            memo[0][j] = j

        for i in range(1, rows + 1):
            for j in range(1, cols + 1):
                if word1[i - 1] == word2[j - 1]:
                    memo[i][j] = memo[i-1][j-1]
                else:
                    left = memo[i - 1][j]
                    down = memo[i][j-1]
                    left_down = memo[i - 1][j - 1]
                    memo[i][j] = min(left, down, left_down) + 1
        return memo[rows][cols]

這一版的定義和自頂向下是反過來的，看的是前綴而不是後綴：

memo[i][j] = 把 word1 的前 i 個字變成 word2 的前 j 個字最少要幾次操作

所以邊界也跟著翻面 —— 從「還剩幾個字」變成「已經有幾個字」：memo[i][0] = i 是把前 i 個字全刪光，memo[0][j] = j 是從空字串插出 j 個字。答案在右下角 memo[rows][cols]。

表格裡三個來源對應的還是同樣三種操作，只是方向反過來看：

程式碼	格子	操作
`left`	`memo[i-1][j]`	刪掉 `word1` 的第 `i` 個字
`down`	`memo[i][j-1]`	插入 `word2` 的第 `j` 個字
`left_down`	`memo[i-1][j-1]`	把第 `i` 個字替換成第 `j` 個字

索引要 -1 是因為 memo 比字串多一排一列，memo[i][j] 裡的 i 是「幾個字」而不是「第幾格」。

補充

兩個可以拿掉的判斷

自頂向下的第一個 base case 是多餘的。 i == len(word1) and j == len(word2) 這條被下一條涵蓋了 —— 走到 i == len(word1) 時回傳 len(word2) - j，而 j 也到底的話這個值本來就是 0。拿掉之後跑 4000 組隨機字串，答案完全一樣。

自底向上開頭的 if rows == 0 or cols == 0 也是多餘的。 空字串已經被邊界初始化處理掉了：rows == 0 時 memo 只有一排，memo[0][j] = j 填完之後兩層迴圈根本不會進去，直接回傳 memo[0][cols]，就是 cols，跟 rows + cols 相同。同樣 4000 組測資驗過。

兩個都不是錯，只是寫的時候還沒發現邊界已經幫忙擋掉了。

複雜度

設 $m$ 是 word1 的長度、 $n$ 是 word2 的長度。

自頂向下

時間 $O (m \times n)$ — 狀態是 (i, j)，共 $(m + 1) (n + 1)$ 個，每個狀態只做常數次比較
空間 $O (m \times n)$ — cache 的大小；另外遞迴深度最深是 $O (m + n)$ ，每層至少讓一個指針前進

自底向上

時間 $O (m \times n)$ — 把整張表填滿，每格 $O (1)$
空間 $O (m \times n)$ — 表格大小，而且沒有遞迴堆疊

兩種寫法的上界完全相同，差別只在遞迴堆疊，以及自頂向下只會算到真正用得到的狀態 —— 相同的字元越多跳得越兇，abcdefgh 對 abcdefgh 只算了 9 個狀態而不是 81 個；反過來兩個字串完全不同時，該算的一個都跑不掉。