我太小看面试难度了，本来以为这样的题目不会遇到，但是小米面试的时候遇到了，好在没做出来也过了，所以一定要搞懂啊。
题目
给定两个字符串S和T，对于T我们允许三种操作：
(1) 在任意位置添加任意字符
(2) 删除存在的任意字符
(3) 修改任意字符
问最少操作多少次可以把字符串T变成S？
例如： S＝ “ABCF” T = “DBFG”
那么我们可以
(1) 把D改为A
(2) 删掉G
(3) 加入C
所以答案是3。
思路
还是百度百科的例子，比如要计算cafe和coffee的编辑距离。cafe→caffe→coffe→coffee
先创建一个6×8的表（cafe长度为4，coffee长度为6，各加2）
image.png
接着，在如下位置填入数字（表2）：
image.png
从3,3格开始，开始计算。取以下三个值的最小值：
如果最上方的字符等于最左方的字符，则为左上方的数字。否则为左上方的数字+1。（对于3,3来说为0）
左方数字+1（对于3,3格来说为2）
上方数字+1（对于3,3格来说为2）
按照这个原理，我们得出下表：
image.png
解法
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];
}
转载自
作者：冯奕欢
链接：https://www.jianshu.com/p/4f0eb339bd7a
來源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
