Edit Distance

題目描述

給定兩個字串 word1 和 word2，回傳將 word1 轉換為 word2 所需的最少操作數。每次可以插入、刪除或替換一個字元。

輸入：word1 = "horse", word2 = "ros"
輸出：3
解釋：horse → rorse（替換 h→r）→ rose（刪除 r）→ ros（刪除 e）

輸入：word1 = "intention", word2 = "execution"
輸出：5

解題思路

定義狀態

dp[i][j] = word1[0..i-1] 轉換成 word2[0..j-1] 的最少操作數

邊界條件

dp[i][0] = i（全刪除），dp[0][j] = j（全插入）

字元相同

dp[i][j] = dp[i-1][j-1]（不需要操作）

字元不同

dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

三種操作

刪除=dp[i-1][j], 插入=dp[i][j-1], 替換=dp[i-1][j-1]

程式碼

C#

csharp

public class Solution {
    public int MinDistance(string word1, string word2) {
        int m = word1.Length, n = word2.Length;
        int[] dp = new int[n + 1];
        
        // 初始化：空字串到 word2[0..j-1] 需要 j 次插入
        for (int j = 0; j <= n; j++) dp[j] = j;
        
        for (int i = 1; i <= m; i++) {
            int prev = dp[0]; // dp[i-1][j-1]
            dp[0] = i;        // 空字串需要 i 次刪除
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (word1[i - 1] == word2[j - 1]) {
                    dp[j] = prev;
                } else {
                    dp[j] = 1 + Math.Min(Math.Min(dp[j], dp[j - 1]), prev);
                    // dp[j]=刪除, dp[j-1]=插入, prev=替換
                }
                prev = temp;
            }
        }
        return dp[n];
    }
}

TypeScript

typescript

function minDistance(word1: string, word2: string): number {
    const m = word1.length, n = word2.length;
    const dp: number[][] = Array.from({length: m + 1}, (_, i) =>
        Array.from({length: n + 1}, (_, j) => (i === 0 ? j : j === 0 ? i : 0))
    );
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j],     // 刪除
                    dp[i][j - 1],     // 插入
                    dp[i - 1][j - 1]  // 替換
                );
            }
        }
    }
    return dp[m][n];
}

Python

python

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = list(range(n + 1))  # dp[j] = j（初始化）
    
    for i in range(1, m + 1):
        prev = dp[0]
        dp[0] = i
        for j in range(1, n + 1):
            temp = dp[j]
            if word1[i - 1] == word2[j - 1]:
                dp[j] = prev
            else:
                dp[j] = 1 + min(dp[j], dp[j - 1], prev)
            prev = temp
    
    return dp[n]

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(m × n) | O(n)（空間優化後） |

圖解

字元相同

直接繼承→

字元不同

替換→

dp[i-1][j-1] (替換/不動)

+0→

dp[i-1][j] (刪除)

min+1→

dp[i][j-1] (插入)

min+1→

dp[i][j]

進階觀點

💡面試追問

Edit Distance（Levenshtein Distance）在拼字檢查、DNA 比對、搜尋引擎模糊匹配中廣泛使用。
如果要輸出具體的操作序列，需要從 dp 表格反向追溯。
583. Delete Operation for Two Strings 是只允許刪除的簡化版本，等價於 m + n - 2 × LCS。
進階優化：如果兩個字串長度差很大，可以只計算對角帶狀區域（Ukkonen's algorithm）。

理解測驗

🤔 dp[i-1][j] + 1 對應哪種操作？

🤔 為什麼字元相同時不需要額外操作（dp[i][j] = dp[i-1][j-1]）？