这个算法是我面试的时候遇到了，觉得很有趣，也很实用，故收纳到我的记录中。
原理
百度百科的解释：
编辑距离（Edit Distance），又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。一般来说，编辑距离越小，两个串的相似度越大。
例如将kitten一字转成sitting：
sitten （k→s）
sittin （e→i）
sitting （→g）
算法
还是百度百科的例子，比如要计算cafe和coffee的编辑距离。cafe→caffe→coffe→coffee
先创建一个6×8的表（cafe长度为4，coffee长度为6，各加2）
接着，在如下位置填入数字（表2）：
从3,3格开始，开始计算。取以下三个值的最小值：
如果最上方的字符等于最左方的字符，则为左上方的数字。否则为左上方的数字+1。（对于3,3来说为0）
左方数字+1（对于3,3格来说为2）
上方数字+1（对于3,3格来说为2）
按照这个原理，我们得出下表：
Java实现
原理很简单，我们看看在Java怎么实现。
public static int ld(String s, String t) {
int d[][];
int sLen = s.length();
int tLen = t.length();
int si;
int ti;
char ch1;
char ch2;
int cost;
if(sLen == 0) {
return tLen;
}
if(tLen == 0) {
return sLen;
}
d = new int[sLen+1][tLen+1];
for(si=0; si<=sLen; si++) {
d[si][0] = si;
}
for(ti=0; ti<=tLen; ti++) {
d[0][ti] = ti;
}
for(si=1; si<=sLen; si++) {
ch1 = s.charAt(si-1);
for(ti=1; ti<=tLen; ti++) {
ch2 = t.charAt(ti-1);
if(ch1 == ch2) {
cost = 0;
} else {
cost = 1;
}
d[si][ti] = Math.min(Math.min(d[si-1][ti]+1, d[si][ti-1]+1),d[si-1][ti-1]+cost);
}
}
return d[sLen][tLen];
}
附加一个相似度函数：
public static double similarity(String src, String tar) {
int ld = ld(src, tar);
return 1 - (double) ld / Math.max(src.length(), tar.length());
} 