LeetCode 72 - Edit 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（全插）
• 轉移：
  • 若 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]
  • 否則取三操作最小值 +1：
    • 刪除 word1[i-1]：dp[i-1][j]
    • 插入 word2[j-1]：dp[i][j-1]
    • 替換：dp[i-1][j-1]

代碼

int minDistance(string a, string b) {
    int n = a.size(), m = b.size();
    vector> dp(n+1, vector(m+1));
    for (int i = 0; i <= n; ++i) dp[i][0] = i;
    for (int j = 0; j <= m; ++j) dp[0][j] = j;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
    return dp[n][m];
}

空間優化

僅依賴上一行，可壓縮為兩個一維陣列 O(min(n,m)) 空間。