学步园

对于两个不同的字符串，我们有一套操作方法来把他们变得相同，具体方法为：

修改一个字符（如把“a”替换为“b”）
删除一个字符（如把“traveling”变为“travelng”）

比如对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。无论增加还是减少“g”，我们都仅仅需要一次操作。我们把这个操作所需要的次数定义为两个字符串的距离LevenshteinDistance(LD)。

Levenshtein distance最先是由俄国科学家VladimirLevenshtein在1965年发明，用他的名字命名。不会拼读，可以叫它editdistance（编辑距离）。

求编辑距离的代码如下：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int similarity(char* str1, char* str2)
{
        if(strlen(str1)==0)
                return strlen(str2);
        else if(strlen(str2)==0)
                return strlen(str1);
        else if( *str1 == *str2 ) // this step is very important!
                return similarity(str1+1, str2+1) ;
        else // if( *str1!=*str2 ) then we have the following
                return  min( min( 1+similarity(str1+1, str2),
                            1+similarity(str1, str2+1) ),
                        1+similarity(str1+1, str2+1) );
}

int main() {
        int dist = similarity("abef","abcdef" );
        printf("%d\n", dist);
}