跳转至

Edit Distance (編輯距離) 🟡 Medium

📌 LeetCode #72 — 題目連結 | NeetCode 解說

1. 🧐 Problem Dissection (釐清問題)

給兩個字串 word1 和 word2。 請計算將 word1 轉換成 word2 所需的 最少操作次數。 允許的操作有三種：

  1. Insert a character (插入)
  2. Delete a character (刪除)

  3. Replace a character (替換)

  4. Input: word1 = "horse", word2 = "ros"

  5. Output: 3
    • horse -> rorse (replace 'h' with 'r')
    • rorse -> rose (remove 'r')
    • rose -> ros (remove 'e')
  6. Input: word1 = "intention", word2 = "execution"
  7. Output: 5
  8. Constraints:
    • \(0 <= word1.length, word2.length <= 500\)

2. 🐢 Brute Force Approach (暴力解)

Recursion: minDist(i, j): min distance between word1[i:] and word2[j:].

  • If word1[i] == word2[j]:
    • minDist(i+1, j+1) (Match)
  • If word1[i] != word2[j]: 1 + min(
    • minDist(i, j+1) (Insert: word1 stays at i, word2 moves j)
    • minDist(i+1, j) (Delete: word1 moves i, word2 stays j)
    • minDist(i+1, j+1) (Replace)
    • )
  • Time: \(O(3^N)\).

3. 💡 The "Aha!" Moment (優化)

標準的 2D DP (Levenshtein Distance)。 dp[i][j] 表示 word1 前 i 個字元和 word2 前 j 個字元的最少操作數。

Transition:

  1. 如果 word1[i-1] == word2[j-1]:
    • 不需要操作，直接繼承：dp[i][j] = dp[i-1][j-1]
  2. 如果不相等：
    • dp[i][j] = 1 + min(
      • dp[i][j-1] (Insert into word1 to match word2[j-1])
      • dp[i-1][j] (Delete from word1)
      • dp[i-1][j-1] (Replace)
      • )

Base Case:

  • dp[i][0] = i (word2 為空，word1 需刪除 i 次)
  • dp[0][j] = j (word1 為空，word1 需插入 j 次)

🎬 Visualization (演算法視覺化)

⤢ 全螢幕開啟視覺化

4. 💻 Implementation (程式碼)

Approach: 2D DP

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length();
        int n = word2.length();

        // dp[i][j]
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        // Base cases
        for (int i = 0; i <= m; i++) dp[i][0] = i; // Delete all chars
        for (int j = 0; j <= n; j++) dp[0][j] = j; // Insert all chars

        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]; // No op needed
                } else {
                    dp[i][j] = 1 + min({
                        dp[i - 1][j],    // Delete
                        dp[i][j - 1],    // Insert
                        dp[i - 1][j - 1] // Replace
                    });
                }
            }
        }

        return dp[m][n];
    }
};

Python Reference

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[float("inf")] * (len(word2) + 1) for i in range(len(word1) + 1)]

        for j in range(len(word2) + 1):
            dp[len(word1)][j] = len(word2) - j
        for i in range(len(word1) + 1):
            dp[i][len(word2)] = len(word1) - i

        for i in range(len(word1) - 1, -1, -1):
            for j in range(len(word2) - 1, -1, -1):
                if word1[i] == word2[j]:
                    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[0][0]
Note: Python solution uses backward DP (filling from bottom-right), C++ uses standard forward DP. Both are valid.

5. 📝 Detailed Code Comments (詳細註解)

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length();
        int n = word2.length();

        // dp[i][j] = 將 word1 前 i 個字元 轉換成 word2 前 j 個字元 的最小步數
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        // Base case initialization
        // 當 word2 是空字串 (j=0)，word1 必須刪除所有 i 個字元
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        // 當 word1 是空字串 (i=0)，word1 必須插入所有 j 個字元
        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++) {
                // 如果當前字元相同 (注意 index 是 i-1, j-1)
                if (word1[i-1] == word2[j-1]) {
                    // 不需要做操作，繼承左上角
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    // 如果不同，取三種操作的最小值 + 1
                    dp[i][j] = 1 + min({
                        dp[i-1][j],    // Delete (刪除 word1[i-1])，狀態回到 i-1, j
                        dp[i][j-1],    // Insert (在 word1 後插入 word2[j-1])，狀態回到 i, j-1
                        dp[i-1][j-1]   // Replace (將 word1[i-1] 換成 word2[j-1])，狀態回到 i-1, j-1
                    });
                }
            }
        }

        return dp[m][n];
    }
};

6. 📊 Rigorous Complexity Analysis (複雜度分析)

  • Time Complexity: \(O(M \times N)\)
    • \(500 \times 500 = 2.5 \times 10^5\). Fast.
  • Space Complexity: \(O(M \times N)\)
    • Can be optimized to \(O(\min(M, N))\) using 1D array (but need prev_diag var).

7. 💼 Interview Tips (面試技巧)

🎯 Follow-up 問題

面試官可能會問的延伸問題：

  • 你會如何處理更大的輸入？
  • 有沒有更好的空間複雜度？

🚩 常見錯誤 (Red Flags)

避免這些會讓面試官扣分的錯誤：

  • ⚠️ 沒有考慮邊界條件
  • ⚠️ 未討論複雜度

✨ 加分項 (Bonus Points)

這些會讓你脫穎而出：

  • 💎 主動討論 trade-offs
  • 💎 提供多種解法比較

站內相關