# 字符串編輯距離 ## 題目描述 給定一個源串和目標串，能夠對源串進行如下操作： 1. 在給定位置上插入一個字符 2. 替換任意字符 3. 刪除任意字符 寫一個程序，返回最小操作數，使得對源串進行這些操作后等于目標串，源串和目標串的長度都小于2000。 ### 分析與解法 此題常見的思路是動態規劃，假如令dp[i][j] 表示源串S[0…i] 和目標串T[0…j] 的最短編輯距離，其邊界：dp[0][j] = j，dp[i][0] = i，那么我們可以得出狀態轉移方程： - dp[i][j] =min{ - dp[i-1][j] + 1 , S[i]不在T[0…j]中 - dp[i-1][j-1] + 1/0 , S[i]在T[j] - dp[i][j-1] + 1 , S[i]在T[0…j-1]中 } 接下來，咱們重點解釋下上述3個式子的含義 - 關于dp[i-1][j] + 1, s.t. s[i]不在T[0…j]中的說明 - s[i]沒有落在T[0…j]中，即s[i]在中間的某一次編輯操作被刪除了。因為刪除操作沒有前后相關性，不妨將其在第1次操作中刪除。除首次操作時刪除外，后續編輯操作是將長度為i-1的字符串，編輯成長度為j的字符串：即dp[i-1][j]。 - 因此：dp[i][j] = dp[i-1][j] + 1。 - 關于dp[i-1][j-1] + 0/1, s.t. s[i] 在T[j]的說明 - 若s[i]經過編輯，最終落在T[j]的位置。 - 則要么s[i] == t[j]，s[i]直接落在T[j]。這種情況，編輯操作實際上是將長度為i-1的S’串，編輯成長度為j-1的T’串：即dp[i-1][j-1]； - 要么s[i] ≠ t[j]，s[i] 落在T[j]后，要將s[i]修改成T[j]，即在上一種情況的基礎上，增加一次修改操作：即dp[i-1][j-1] + 1。 - 關于dp[i][j-1] + 1, s.t. s[i]在T[0…j-1]中的說明 - 若s[i]落在了T[1…j-1]的某個位置，不妨認為是k，因為最小編輯步數的定義，那么，在k+1到j-1的字符，必然是通過插入新字符完成的。因為共插入了(j-k)個字符，故編輯次數為(j-k)次。而字符串S[1…i]經過編輯，得到了T[1…k]，編輯次數為dp[i][k]。故： dp[i][j] = dp[i][k] + (j-k)。 - 由于最后的(j-k)次是插入操作，可以講(j-k)逐次規約到dp[i][k]中。即：dp[i][k]+(j-k)=dp[i][k+1] + (j-k-1) 規約到插入操作為1次，得到 dp[i][k]+(j-k) =dp[i][k+1] + (j-k-1) =dp[i][k+2] + (j-k-2)=… =dp[i][k+(j-k-1)] + (j-k)-(j-k-1) =dp[i][j-1] + 1。 上述的解釋清晰規范，但為啥這樣做呢？ 換一個角度，其實就是字符串對齊的思路。例如把字符串“ALGORITHM”，變成“ALTRUISTIC”，那么把相關字符各自對齊后，如下圖所示：  把圖中上面的源串S[0…i] = “ALGORITHM”編輯成下面的目標串T[0…j] = “ALTRUISTIC”，我們枚舉字符串S和T最后一個字符s[i]、t[j]對應四種情況：（字符-空白）（空白-字符）(字符-字符)（空白-空白）。 由于其中的（空白-空白）是多余的編輯操作。所以，事實上只存在以下3種情況： - 下面的目標串空白，即S + 字符X，T + 空白，S變成T，意味著源串要刪字符 - dp[i - 1, j] + 1 - 上面的源串空白，S + 空白，T + 字符，S變成T，最后，在S的最后插入“字符”，意味著源串要添加字符 - dp[i, j - 1] + 1 - 上面源串中的的字符跟下面目標串中的字符不一樣，即S + 字符X，T + 字符Y，S變成T，意味著源串要修改字符 - dp[i - 1, j - 1] + (s[i] == t[j] ? 0 : 1) 綜上，可以寫出簡單的DP狀態方程： ```c //dp[i,j]表示表示源串S[0…i] 和目標串T[0…j] 的最短編輯距離 dp[i, j] = min { dp[i - 1, j] + 1, dp[i, j - 1] + 1, dp[i - 1, j - 1] + (s[i] == t[j] ? 0 : 1) } //分別表示：刪除1個，添加1個，替換1個（相同就不用替換）。 ``` 參考代碼如下： ```c //dp[i][j]表示源串source[0-i)和目標串target[0-j)的編輯距離 int EditDistance(char *pSource, char *pTarget) { int srcLength = strlen(pSource); int targetLength = strlen(pTarget); int i, j; //邊界dp[i][0] = i，dp[0][j] = j for (i = 1; i <= srcLength; ++i) { dp[i][0] = i; } for (j = 1; j <= targetLength; ++j) { dp[0][j] = j; } for (i = 1; i <= srcLength; ++i) { for (j = 1; j <= targetLength; ++j) { if (pSource[i - 1] == pTarget[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]); } } } return dp[srcLength][targetLength]; } ``` ## 舉一反三 1、傳統的編輯距離里面有三種操作，即增、刪、改，我們現在要討論的編輯距離只允許兩種操作，即增加一個字符、刪除一個字符。我們求兩個字符串的這種編輯距離，即把一個字符串變成另外一個字符串的最少操作次數。假定每個字符串長度不超過1000，只有大寫英文字母組成。 2、有一億個數，輸入一個數，找出與它編輯距離在3以內的數，比如輸入6（0110），找出0010等數，數是32位的。 ## 問題擴展 實際上，關于這個“編輯距離”問題在搜索引擎中有著重要的作用，如搜索引擎關鍵字查詢中拼寫錯誤的提示，如下圖所示，當你輸入“[Jult](https://www.google.com.hk/search?hl=zh-CN&newwindow=1&safe=strict&site=&source=hp&q=Jult&btnK=Google+%E6%90%9C%E7%B4%A2)”后，因為沒有這個單詞“Jult”，所以搜索引擎猜測你可能是輸入錯誤，進而會提示你是不是找“July”：  當然，面試官還可以繼續問下去，如請問，如何設計一個比較這篇文章和上一篇文章相似性的算法？