Edit Distance

題目

給定兩字串 s 和 t，求出 s 轉成 t 的最少編輯次數。

解法

暫時不考慮 Copy & Twiddle，因為會需要中介字串 z 以及定義上會小小複雜，這裡用不到。
假設替換、刪除和插入的編輯成本皆為 1。

定義 D[i, j] 為字串 s[i: len(s)] 轉成字串 t[j: len(t)] 的最少編輯次數。
若

$s[i]=t[j]$，則不用編輯，D[i, j] = D[i + 1, j + 1]。
若

$s[i]\ne t[j]$，則考慮以下情況 :
Case 1: 替換，將字元 s[i] 替換成 t[j]，問題縮小成將字串 s[i + 1: len(s)] 轉成 t[j + 1: len(t)]，所以編輯次數為 D[i, j] = 1 + D[i + 1, j + 1]。

Case 2: 刪除，刪除字元 s[i]，則問題縮小成將字串 s[i + 1: len(s)] 轉成 t[j: len(t)]，所以編輯次數為 D[i, j] = 1 + D[i + 1, j]。

Case 3: 插入，將 t[j] 插入 s[i] 之前，則問題縮小成將字串 s[i: len(s)] 轉成 t[j + 1: len(t)]，所以編輯次數為 D[i, j] = 1 + D[i, j + 1]。

Case 4: Twiddle，交換字元 s[i] 和 s[i + 1] 的位置，則問題縮小成將字串 s[i + 2: len(s)] 轉成 t[j + 2: len(t)]，需要一個暫存變數 temp 來交換，所以編輯次數為 D[i, j] = 3 + D[i + 2, j + 2]。

取出 Case 1 ~ 4 的最小值，即為 D[i, j] = min(1 + D[i + 1, j + 1], 1 + D[i + 1, j + 1], 1 + D[i, j + 1], 3 + D[i + 2, j + 2])

邊界條件 :

1. 若兩字串為空字串，則編輯次數為 0。
2. 若 t 為空字串，s 不為空字串，則編輯次數為 len(s)，即刪除 len(s) 個字元就能變成空字串。
3. 若 s 為空字串，t 不為空字串，則編輯次數為 len(t)，即插入 len(t) 個字元就能變成 t 字串。

• clrs solution : 有複製和交換功能，含中介字串 z

遞迴式

實作