LeetCode 編輯距離：動態規劃求字符串最小編輯操作數

題目描述

給定兩個單詞 word1、word2，求將 word1 轉換為 word2 的最小操作數。允許操作：插入、刪除、替換字符。

範例：

輸入: word1 = "heo", word2 = "hello"
輸出: 2 (插入 'l', 'l')

解題思路：二維動態規劃

dp[i][j] 表示 word1[0..i-1] 轉換為 word2[0..j-1] 的最小編輯距離。

最後一步操作三種情況：

1. 刪除 word1[i-1]：dp[i-1][j] + 1
2. 插入 word2[j-1]：dp[i][j-1] + 1
3. 替換/保留 word1[i-1] → word2[j-1]：dp[i-1][j-1] + (word1[i-1] != word2[j-1])

狀態轉移：dp[i][j] = min(上述三項)

初始化：dp[0][j] = j（全插入）、dp[i][0] = i（全刪除）。

時間複雜度：O(mn)，空間複雜度：O(mn)（可優化至 O(min(m,n))）。

Python 參考實現

class Solution:
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        m, n = len(word1), len(word2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        
        for j in range(m + 1):
            dp[0][j] = j
        for i in range(n + 1):
            dp[i][0] = i
        
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                cost = 0 if word1[j-1] == word2[i-1] else 1
                dp[i][j] = min(
                    dp[i-1][j] + 1,      # 刪除
                    dp[i][j-1] + 1,      # 插入
                    dp[i-1][j-1] + cost  # 替換/保留
                )
        return dp[n][m]

# 測試
if __name__ == "__main__":
    sol = Solution()
    assert sol.minDistance("", "a") == 1
    assert sol.minDistance("faf", "efef") == 2
    assert sol.minDistance("horse", "ros") == 3
    assert sol.minDistance("intention", "execution") == 5
    print("所有測試通過")

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

    def minDistance(self, word1, word2):
        if len(word1) > len(word2):
            word1, word2 = word2, word1  # 確保 word1 較短
        m, n = len(word1), len(word2)
        prev = list(range(m + 1))
        for i in range(1, n + 1):
            curr = [i] + [0] * m
            for j in range(1, m + 1):
                cost = 0 if word1[j-1] == word2[i-1] else 1
                curr[j] = min(prev[j] + 1, curr[j-1] + 1, prev[j-1] + cost)
            prev = curr
        return prev[m]

核心要點總結

• 經典 DP 模型：字符串編輯距離是二維 DP 入門必修題
• 三操作對應：橫向=插入、縱向=刪除、斜向=替換
• 空間優化：僅依賴上一行，滾動數組降維
• 應用場景：拼寫糾錯、DNA 序列比對、版本控制 diff、NLP 相似度

編輯距離（Levenshtein Distance）是字符串相似度度量的基石，掌握其 DP 結構與優化技巧，是解決序列比對問題的關鍵。