编辑距离

2021-03-11

字数：418字 | 预计阅读时长：2分钟

编辑距离

static int editDist(String str1 , String str2 , int m ,int n){

    if (str1.charAt(m-1) == str2.charAt(n-1))
        return editDist(str1, str2, m-1, n-1);

    return 1 + min ( editDist(str1,  str2, m, n-1),    // Insert
                     editDist(str1,  str2, m-1, n),   // Remove
                     editDist(str1,  str2, m-1, n-1) // Replace                     
                   ); //三个子问题
    }

//s: beforeediting,length=n  t: afterediting,length=m
//d: recording the distance
        d = new int[n + 1][m + 1];  
              
        for (i = 0; i <= n; i++) {  
            d[i][0] = i;  
        }  
        for (j = 0; j <= m; j++) {  
            d[0][j] = j;  
        }  
          
         
        for (i = 1; i <= n; i++) {  
            s_i = s.charAt(i - 1);  
              
            for (j = 1; j <= m; j++) {  
                t_j = t.charAt(j - 1);  
                 
                cost = (s_i == t_j) ? 0 : 1;  
                 
                d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1,  
                        d[i - 1][j - 1] + cost);  
            }  
        }

if x == y, then d[i][j] == d[i-1][j-1]
if x != y, 插入y则 d[i][j] = d[i][j-1] + 1
if x != y, 删除x则 d[i][j] = d[i-1][j] + 1
if x != y, x改变为y则 d[i][j] = d[i-1][j-1] + 1
When x!=y, d[i][j] 取三中编辑方式最小代价。
初始化条件 ： d[i][0] = i, d[0][j] = j

为什么不同操作就是对应与d的左移上移或左上移？
这个问题递归角度较易理解。
DP角度，d记录的是目前最小编辑距离。左、上、左上为子问题，即儿子。若为插入，则j需+1得到t的下一个字符，而x继续与此字符比较，i不变。
由递归到DP，实质就是找到递归中子问题。
找到后，将子问题结果记录在数组即可。

本文作者： yuqing wang
本文链接： https://satyrswang.github.io/2021/03/11/编辑距离/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！