72、最小编辑距离

我太小看面试难度了，本来以为这样的题目不会遇到，但是小米面试的时候遇到了，好在没做出来也过了，所以一定要搞懂啊。

题目

给定两个字符串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
來源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。