算法：编辑距离（Levenshtein Distance）

1. 什么是“编辑距离” ？

“编辑距离”又称 Leveinshtein 距离，是由俄罗斯科学家 Vladimir Levenshtein 在 1965 年提出。

“编辑距离”是计算两个文本相似度的算法之一，字符串 X 和字符串 Y 的编辑距离是将 X 转换成 Y 的最小操作次数，这里的操作包括三种：

• 插入一个字符
• 删除一个字符
• 替换一个字符

例如：

kitten 和 sitting 的编辑距离是3。

1. kitten -> sitten (k替换为s)
2. sitten -> sittin (e替换为i)
3. sittin -> sitting (插入g)

至少要做3次操作。

图文无关：从入门到放弃

2. 基本策略 ？

... 当然还是传说中的 ...

线性规划

图文无关

递推公式如下

3. 程序代码 ？

4. 特性分析

• 时间复杂度：O(m*n)