LeetCode Edit Distance：編輯距離動態規劃詳解與空間優化

LeetCode Edit Distance：編輯距離動態規劃詳解與空間優化

給定兩字符串 word1, word2，允許操作：**插入**、**刪除**、**替換**（代價均為 1）。求將 word1 轉換為 word2 的最小操作數。

DP 定義

dp[i][j] = word1[0…i-1] 轉換為 word2[0…j-1] 的最小編輯距離。
i = 0…m, j = 0…n。

轉移方程

dp[0][j] = j          // 空串 → 長 j 串：j 次插入
dp[i][0] = i          // 長 i 串 → 空串：i 次刪除

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],     // 刪除 word1[i-1]
        dp[i][j-1],     // 插入 word2[j-1]
        dp[i-1][j-1]    // 替換 word1[i-1] → word2[j-1]
    );

完整 C++ 實現（二維 DP）

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

空間優化：滾動數組 O(min(m,n))

dp[i][*] 僅依賴 dp[i-1][*] 和 dp[i][j-1]，用**兩行**滾動：

int minDistance(string a, string b) {
    if (a.size() < b.size()) swap(a, b);  // 保證 b 較短，空間 O(|b|)
    int m = a.size(), n = b.size();
    vector<int> prev(n+1), curr(n+1);
    iota(prev.begin(), prev.end(), 0);  // prev[j] = j
    for (int i = 1; i <= m; ++i) {
        curr[0] = i;
        for (int j = 1; j <= n; ++j) {
            if (a[i-1] == b[j-1]) curr[j] = prev[j-1];
            else curr[j] = 1 + min({prev[j], curr[j-1], prev[j-1]});
        }
        swap(prev, curr);
    }
    return prev[n];
}

關鍵點

1. 替換 = 刪除 + 插入：代價均為 1 時等價，故方程中三者並列。
2. 初始化：dp[0][j]=j, dp[i][0]=i 反映空串轉換基礎代價。
3. 滾動順序：curr[j] 依賴 prev[j] (上)、curr[j-1] (左)、prev[j-1] (左上)，故 j 正序遍歷即可。
4. 交換優化：令內層循環對應較短串，空間降至 O(min(m,n))。

複雜度

• 時間：O(m·n)。
• 空間：二維 O(m·n)，滾動 O(min(m,n))。

應用擴展

• 輸出具體操作序列：回溯 dp 表，記錄選擇來源（刪/插/替/匹配）。
• 不同操作代價：修改方程中三項權重。
• 近似字符串匹配：允許編輯距離 ≤ k 的模糊查找。
• DNA 序列比對：生物信息學核心算法（Needleman-Wunsch 全局比對即編輯距離變體）。

總結

編輯距離是二維 DP的經典範例：最優子結構明確（前綴轉換決定整體）、重疊子問題顯著。掌握 dp[i][j] 定義、三種操作轉移、滾動數組優化，即可解決所有字符串相似度問題。LeetCode 72 是該模型的標準練習題。