【动态规划】字符串编辑距离（Levenshtein距离）算法
基本介绍
Levenshtein距离是一种计算两个字符串间的差异程度的字符串度量（string metric）。我们可以认为Levenshtein距离就是从一个字符串修改到另一个字符串时，其中编辑单个字符（比如修改、插入、删除）所需要的最少次数。俄罗斯科学家Vladimir Levenshtein于1965年提出了这一概念。
简单例子
从字符串“kitten”修改为字符串“sitting”只需3次单字符编辑操作，如下：
- sitten ( k -> s )
- sittin ( e -> i )
- sitting ( _ -> g )
实现思想
如何编程实现这一算法呢？许多人试图用矩阵来解释，但实际上矩阵是最终可视化的工具，配合理解“为什么”比较方便，但从矩阵却比较难想到“怎么做”。
我们试图找到“从字符串A修改到字符串B”这一问题的子解结构。当然反过来说“从字符串B修改到字符串A”和它是同一个问题，因为从A中删掉一个字符来匹配B，就相当于在B中插入一个字符来匹配A，这两个操作是可以互相转化的。
假设字符序列A[1…i]、B[1…j]分别是字符串A、B的前i、j个字符构成的子串，我们得到一个子问题是“从字符串A[1…i]修改到字符串B[1…j]”：
文章图片
① 插入操作： 当将]A[1…i]修改成B[1…j?1]需要操作数为op1，那么我插入一个字符A[i’]=B[i]到A[i]和A[i+1]之间，用以匹配B[i]，于是A[1…i]修改到B[1…j]所需操作数为op1?? +1。
文章图片
② 删除操作： 当将A[1…i?1]修改成B[1…j]需要操作数为op2 ，那么我删掉字符A[i]也可以op?2?? +1的操作数使两个子字符串匹配：
文章图片
③ 修改操作： 如果A[1…i?1]修改成B[1…j?1]所需操作数为op?3?? 的话，我将字符A[i]A[i]替换成A[i?′]=B[j]，就可以op?3? +1的操作数完成：
文章图片
但如果此时字符A[i]==B[j]的话，则不需要进行修改操作，操作数仍为op?3?? 。
综上所述，我们将字符串A[1…i]修改成字符串B[1…j]所需操作为 min{ op?1? +1, op?2?? +1, op?3??+1?(a?i?? ≠b?i?? )?? }，其中1?(a?i?? ≠b?i?? )?? 代表当a?i?? ≠b?i?? 时取值1，否则取值为0。
数学定义 数学上，我们定义两个字符串A和B间的Levenshtein距离为levA, B?? (a, b)，其中a、b分别为字符串A、B的长度，而
文章图片
代码
【【动态规划】字符串编辑距离（Levenshtein距离）算法】这题思路明白了，代码自然就会写了（事实上代码也很短）
#include
#define max(x,y) (x>y?x:y)
#define min(x,y) (x 推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长