Levenshtein编辑距离C++实现

admin

简介

Levenshtein Distance是1965年由苏联数学家Vladimir Levenshtein发明的。Levenshtein Distance也被称为编辑距离（Edit Distance）。

在信息论和计算机科学中，Levenshtein Distance是一个度量两个字符序列之间差异的字符串度量标准，两个单词之间的Levenshtein Distance是将一个单词转换为另一个单词所需的单字符编辑（插入、删除或替换）的最小数量。

定义

对于两个字符串a, b

例子

• 1.kitten->sitten(用’s’取代‘k’)
• 2.sitten->sittin(用’i’取代’e’)
• 3.sittin->sitting(在末尾插入’g’)
  

因此距离为3

---

上下界

1.至少总是两个字符串大小的差值；

2.至多是较长字符串的长度；

3.当且仅当两个字符串相等时值为0；

4.如果两个字符串大小相等，汉明距离是其上界；

5.两个字符串的莱文***距离不大于分别与第三个字符串的莱文***距离之和（三角不等式）。

---

C++代码

包含递归与动态规划

动态规划矩阵示意图：

游客，如果您要查看本帖隐藏内容请回复

可以看到DP时间很快

---