字符串编辑距离的计算方法

字符串编辑距离，又称 

Levenshtein距离，

指由一个字符串变成另一个字符串所需的最少的编辑次数，这些编辑操作包括将一个字符替换为另一个字符，删除一个字符和添加一个字。

详细内容可以参考

http://en.wikipedia.org/wiki/Levenshtein_distance

则C++代码实现为：

int minimum(int a,int b,int c) {return min(a,min(b,c)); } int LevenshteinDistance(const char* s, int len_s, const char* t, int len_t) {/* base case: empty strings */if (len_s == 0) return len_t;if (len_t == 0) return len_s;int cost = 0;/* test if last characters of the strings match */if (s[len_s-1] == t[len_t-1])cost = 0;elsecost = 1;/* return minimum of delete char from s, delete char from t, and delete char from both */return minimum(LevenshteinDistance(s, len_s - 1, t, len_t ) + 1,LevenshteinDistance(s, len_s , t, len_t - 1) + 1,LevenshteinDistance(s, len_s - 1, t, len_t - 1) + cost); }

比如由字符串aabab转换成字符串baab通过上面的代码技术得到结果为2.

具体步骤是

第一步，将第一个a替换成b。

第二步，将第二个b删除。

如图所示

总结

以上是生活随笔为你收集整理的字符串编辑距离的计算方法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。