---
title: "72. Edit Distance"
url: "https://laigary.com/interview/coding/72-edit-distance"
type: "note"
section: "coding"
date: "2023-01-28"
updated: "2026-08-01"
tags: ["Dynamic Programming"]
---

# 72. Edit Distance

[72\. Edit Distance](https://leetcode.com/problems/edit-distance/)

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

這一題是真的很難的一道題目，難不是難在怎麼寫，是難在這個最短編輯距離的方式是：俄羅斯科學家弗拉基米爾·萊文斯坦在1965年提出的概念。又稱[萊文斯坦距離（Levenshtein distance）](https://zh.wikipedia.org/wiki/%E8%90%8A%E6%96%87%E6%96%AF%E5%9D%A6%E8%B7%9D%E9%9B%A2)。

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

## 思路

### 狀態就是兩個指針

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

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

答案就是 `dp(0, 0)`。

### 字元相同不用花錢

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

```text
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`：

$$
dp(i, j) = \begin{cases}
dp(i+1,\ j+1) & \text{if } word1[i] = word2[j] \\
1 + \min\bigl(dp(i+1,\ j),\ dp(i,\ j+1),\ dp(i+1,\ j+1)\bigr) & \text{otherwise}
\end{cases}
$$

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

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

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

## 解題方向

### 自頂向下

```python
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` 裡面那三行的順序，就是上面表格的**刪除、插入、替換**。

### 自底向上

```python
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 個；反過來兩個字串完全不同時，該算的一個都跑不掉。