---

LeetCode 72. Edit Distance

題目

72. Edit Distance

解題思路

這題要找出狀態轉移函式直接以二維陣列輔助比較方便理解，下圖以 測資1 為例，橫軸為 word1 字串 ("horse")，縱軸為 word2 字串 ("ros")，這裡先用 'x' 表示二維陣列裡每個欄位的值，等定義好狀態後再填入數字。

    j 0 1 2 3 4
      h o r s e
i    ----------
0 r | x x x x x
1 o | x x x x x
2 s | x x x x x

狀態定義

動態規劃一開始都要先定義狀態，首先假設二維陣列為 dp，那麽 dp[i][j] 表示 word1 的 0 ~ i 個字元與 word2 的 0 ~ j 個字元的最小編輯距離。

舉例

dp[2][1] 表示 "hor" 與 "ro" 的最小編輯距離，dp[2][1] 為 2 (將 "hor" 字串中的 'h' 取代為 'r'，再把最後一個 'r' 刪除)。

以下為二維陣列 dp 每個欄位的最小編輯距離數值：

    j 0 1 2 3 4
      h o r s e
i    ----------
0 r | 1 2 2 3 4
1 o | 2 1 2 3 4
2 s | 3 2 2 2 3

狀態轉移函式

接著要找出狀態轉移函式，dp[i][j] 有兩種情況，分別是 word2[i] 與 word1[j] 相等與不相等 (注意：word2 為縱軸，word1 為橫軸)。在相等的情況下，表示不需要進行任何操作，因此此時的最小編輯距離等於 dp[i-1][j-1]；在不相等的情況下，則有三種操作，分別是插入、刪除、取代，因此最小編輯距離等於 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] 中的最小值再加 1。總結狀態轉移函式如下：

$f(i,j)=\{\begin{array}{rlrl}& f(i-1,j-1)& ,& ifw2[i]==w1[i]\\ & min(f(i-1,j),f(i,j-1),f(i-1,j-1))+1& ,& else\end{array}$

$f(i,j)=\{\begin{array}{rlrl}& f(i-1,j-1)& ,& ifw2[i]==w1[i]\\ & min(f(i-1,j),f(i,j-1),f(i-1,j-1))+1& ,& else\end{array}$

在不相等的情況

這裡補充不相等情況下的思路，首先既然 word2[i] 與 word1[j] 不相等，那麼就需要進行操作讓這兩個字串相等，為了清楚說明情況，因此再放一次 測資1 的二維陣列 dp 且填上每個欄位的最小編輯距離數值，並且依序來探討題目給的三種操作方式 (插入、刪除、取代)。

    j 0 1 2 3 4
      h o r s e
i    ----------
0 r | 1 2 2 3 4
1 o | 2 1 2 3 4
2 s | 3 2 2 2 3

以下 word1 表示 "horse"，word2 表示 "ros"。

• 插入

  插入的操作是從 dp[i - 1][j] + 1 到 dp[i][j] 的過程，也就是插入 word2[i] 的字元到最後面。以 dp[2][1] 為例，這是 "ho" 轉換成 "ros" 的最小編輯距離，接著我們觀察 dp[1][1]，這是 "ho" 轉換成 "ro" 的最小編輯距離，將 dp[1][1] 狀態轉換成 dp[2][1] 狀態的操作方式是插入 's' 到最後面。

• 刪除

  刪除的操作是從 dp[i][j - 1] + 1 到 dp[i][j] 的過程，也就是刪除 word1[j] 的字元。以 dp[2][1] 為例，這是 "ho" 轉換成 "ros" 的最小編輯距離，接著我們觀察 dp[2][0]，這是 "h" 轉換成 "ros" 的最小編輯距離，將 dp[2][0] 狀態轉換成 dp[2][1] 狀態的操作方式是刪除 'o' 字元。

• 取代

  取代的操作是從 dp[i - 1][j - 1] + 1 到 dp[i][j] 的過程，也就是將 word1[j] 取代為 word2[i]。以 dp[2][2] 為例，這是 "hor" 轉換成 "ros" 的最小編輯距離，接著我們觀察 dp[1][1]，這是 "ho" 轉換成 "ro" 的最小編輯距離，將 dp[1][1] 狀態轉換成 dp[2][2] 狀態的操作方式是把 'r' 取代為 's'。

總結以上三種操作方式，我們可以得知 dp[i][j] 的最小編輯距離等於 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] 中的最小值再加 1 (為什麼是最小值？因為是最小編輯距離，所以要取得當前狀態下最優解)。