LeetCode 筆記：Edit Distance - 編輯距離 (Levenshtein Distance)

題目描述

給定兩個單詞 word1、word2，允許三種操作（各代價 1）：插入、刪除、替換。求將 word1 轉換為 word2 的最小操作次數。

動態規劃：經典二維 DP

定義 dp[i][j]：word1[0..i-1] 轉換為 word2[0..j-1] 的最小編輯距離。
邊界：dp[i][0] = i（全刪除），dp[0][j] = j（全插入）。
轉移：

if (word1[i-1] == word2[j-1])
    dp[i][j] = dp[i-1][j-1];              // 字符相同，無需操作
else
    dp[i][j] = 1 + min(
        dp[i-1][j-1],   // 替換
        dp[i][j-1],     // 插入 (word1 插入 word2[j-1])
        dp[i-1][j]      // 刪除 (刪除 word1[i-1])
    );

代碼實現 (C++ / Java / Python)

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector> dp(m+1, vector(n+1));
        for (int i = 0; i <= m; ++i) dp[i][0] = i;
        for (int j = 0; j <= n; ++j) dp[0][j] = j;
        for (int i = 1; i <= m; ++i)
            for (int 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 + min({dp[i-1][j-1], dp[i][j-1], dp[i-1][j]});
        return dp[m][n];
    }
};

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; ++i) dp[i][0] = i;
        for (int j = 0; j <= n; ++j) dp[0][j] = j;
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                if (word1.charAt(i-1) == word2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j]));
        return dp[m][n];
    }
}

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0]*(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
        for i in range(1, m+1):
            for j in range(1, n+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = 1 + min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])
        return dp[m][n]

空間優化：兩行滾動數組

dp[i][j] 僅依賴 i-1 行和 i 行已計算值，可用兩個一維數組 prev、cur 交替，空間降至 O(min(m,n))。

應用場景

• 拼寫檢查、DNA 序列比對、版本控制差異、自然語言處理相似度。
• 變體：允許交換相鄰字符（Damerau-Levenshtein）、不同操作代價、最長公共子序列 (LCS) 等價於只允許刪除/插入。

複雜度

• 時間：O(m·n)
• 空間：O(m·n) 或 O(min(m,n))

總結

編輯距離是動態規劃的教科書級例題。狀態定義清晰、轉移方程對稱優美。面試必會：能手寫二維 DP、說明三種操作對應的轉移來源、現場優化至兩行滾動數組，並能說出實際應用場景。