在自然語言處理、拼寫糾錯、模糊搜索等場景中，我們經常需要衡量兩個字符串之間的相似度。編輯距離（Edit Distance） 就是一個經典的衡量方式，它描述了將一個字符串轉換為另一個字符串所需的最少操作次數。
一、問題定義：什么是編輯距離？
編輯距離，也稱為 Levenshtein Distance，指的是將字符串 A 轉換成字符串 B 所需的最少操作次數。操作允許：
- ? 插入一個字符（Insert）
- ? 刪除一個字符（Delete）
- ? 替換一個字符（Replace）
示例：
A = "kitten"
B = "sitting"編輯距離 = 3
解釋：
kitten → sitten（k → s） → sittin（e → i）→ sitting（插入 g）二、應用場景
編輯距離廣泛應用于：
- ? 搜索引擎模糊匹配（例如：“gooogle” 應該匹配 “google”）
- ? 拼寫檢查和自動糾正
- ? 語音識別、OCR糾錯
- ? DNA序列比對
三、解決思路：動態規劃（DP）
1. 狀態定義
設 dp[i][j] 表示將字符串 A 的前 i 個字符轉換成字符串 B 的前 j 個字符所需的最小操作數。
2. 狀態轉移方程
我們可以從三個方向轉移過來：
- ? 插入：
dp[i][j-1] + 1（B 多了個字符） - ? 刪除：
dp[i-1][j] + 1（A 多了個字符） - ? 替換或匹配：
dp[i-1][j-1] + cost- ? 如果
A[i-1] == B[j-1]，cost = 0 - ? 否則
cost = 1
- ? 如果
最終狀態轉移為：
dp[i][j] = min(
dp[i-1][j] + 1, // 刪除
dp[i][j-1] + 1, // 插入
dp[i-1][j-1] + cost 
