### 編輯距離算法 概念 > 指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數，如果它們的距離越大，說明它們越是不同。許可的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符。 這個概念是由俄羅斯科學家Vladimir Levenshtein在1965年提出來的，所以也叫 Levenshtein 距離。它可以用來做DNA分析，拼字檢測，抄襲識別等等。總是比較相似的，或多或少我們可以考慮編輯距離。 在概念中，我們可以看出一些重點那就是，編輯操作只有三種。`插入`，`刪除`，`替換`這三種操作，我們有兩個字符串，將其中一個字符串經過上面的這三種操作之后，得到兩個完全相同的字符串付出的代價是什么就是我們要討論和計算的。 舉例說明： 2個個單詞 hello world | | | | | | | | | --- | --- | --- | --- | --- | --- | --- | | | | h | e | l | l | o | | | 0 | 1 | 2 | 3 |4 | 5 | | w | 1 |h≠w <br/> min(1+1,1+1,0+1) = 1| o≠w <br/> min(2+1,2+1,1+1) = 2| 3 |4|5 | | o | 2 |h≠o <br/> min(2+1,1+1,1+1) = 2|2 | 3 | 4 | 4| | r | 3 |h≠r <br/> min(3+1,2+1,2+1) = 3| 3 | 3 | 4| 5 | | l | 4 |h≠l <br/> min(4+1,3+1,3+1) = 4 | 4 | 3 | 3 | 4 | | d | 5 |h≠d <br/> min(5+1,4+1,4+1) = 5 | 5 | 4 | 4| o≠d <br/> min(4+1,4+1,3+1) = 4 |