編輯距離：LeetCode Edit Distance 動態規劃完整解析

問題描述

給定兩個單詞 word1 和 word2，求將 word1 轉換為 word2 所需的最少操作數。允許三種操作：插入一個字符、刪除一個字符、替換一個字符。每種操作代價均為 1。

動態規劃狀態定義

設 dp[i+1][j+1] 表示 word1[0..i] 與 word2[0..j] 的最短編輯距離。為了方便邊界處理，dp 數組大小為 (m+1) × (n+1)，其中 m, n 為兩字符串長度。

狀態轉移方程推導

考慮 word1[i] 和 word2[j] 的關係：

1. 刪除：刪除 word1[i]，問題轉化為 dp[i][j+1] + 1。
2. 插入：在 word1 末尾插入 word2[j]，問題轉化為 dp[i+1][j] + 1。
3. 替換/匹配：
   • 若 word1[i] == word2[j]，無需操作，代價 dp[i][j]。
   • 若不等，替換 word1[i] 為 word2[j]，代價 dp[i][j] + 1。
   統一寫為 dp[i][j] + (word1[i] != word2[j])。

綜合以上三種情況取最小值：

dp[i+1][j+1] = min(
    dp[i][j+1] + 1,              // 刪除
    dp[i+1][j] + 1,              // 插入
    dp[i][j] + (word1[i] != word2[j]) // 替換/匹配
);

初始化與邊界

• dp[i][0] = i：將 word1[0..i-1] 轉為空串，需刪除 i 次。
• dp[0][j] = j：將空串轉為 word2[0..j-1]，需插入 j 次。

完整 C++ 代碼

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 = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                dp[i+1][j+1] = min({
                    dp[i][j+1] + 1,
                    dp[i+1][j] + 1,
                    dp[i][j] + (word1[i] != word2[j])
                });
            }
        }
        return dp[m][n];
    }
};

空間優化：滾動數組

由於 dp[i+1][*] 僅依賴 dp[i][*] 和 dp[i+1][j]，可壓縮為一維數組 dp[n+1]，從左到右更新：

vector<int> dp(n+1);
iota(dp.begin(), dp.end(), 0); // 0,1,2,...,n
for (int i = 0; i < m; ++i) {
    int prev = dp[0]; // 左上角值 dp[i][j]
    dp[0] = i+1;
    for (int j = 0; j < n; ++j) {
        int temp = dp[j+1]; // 保存 dp[i][j+1] 供下輪作為 prev
        dp[j+1] = min({dp[j+1] + 1, dp[j] + 1, prev + (word1[i] != word2[j])});
        prev = temp;
    }
}
return dp[n];

複雜度分析

應用延伸

• 最長公共子序列 (LCS)：僅允許刪除/插入，等價於編輯距離的變體。
• 近似字符串匹配：允許 k 次編輯操作的模式匹配。
• DNA 序列比對：生物信息學核心算法。

總結

編輯距離是動態規劃中最經典的字符串問題之一。掌握其狀態定義、轉移方程推導及空間優化技巧，不僅能解決 LeetCode 72，更能舉一反三解決各類字符串相似度計算問題。關鍵在於理解三種操作對應的子問題關係，並正確處理邊界初始化。