### 编辑距离算法 概念 > 指两个字串之间，由一个转成另一个所需的最少编辑操作次数，如果它们的距离越大，说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。 这个概念是由俄罗斯科学家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 |