最短编辑距离

最短编辑距离

题目

给定两个字符串。定义三种操作： 1.插入一个字符。2.修改一个字符。3.删除一个字符。
求最少几步操作使得第一个字符串变成第二个字符串。

例如：第一个字符串lighten,第二个字符串fighting
fighten (l->f) 修改
fightin (e->i) 修改
fighting (->g) 插入
一共三步

代码

var a=readline();
var b=readline();
var m=a.length;
var n=b.length;
//生成二维数组方法
function DArray(rowLength, colLength) {
            var dArray = new Array(rowLength);
            for (var i = 0; i < rowLength; i++) {
                dArray[i] = new Array(colLength);
            }
            return dArray;
        }
 
var arr =DArray(m+1,n+1);
arr[0][0]=0;
 
 
    for(let i=1;i<=m;i++){
        arr[i][0]=i;
    }
    for(let j=1;j<=n;j++){
        arr[0][j]=j;
    }
    for(var i=1;i<=m;i++){
        for(var j=1;j<=n;j++){
            if(a[i-1]==b[j-1]){
                arr[i][j]=arr[i-1][j-1];
            }else{
                arr[i][j]=Math.min(arr[i-1][j]+1,
                                   arr[i][j-1]+1,
                                   arr[i-1][j-1]+1);
                 
            }
        }
    }
    print(arr[m][n]);

思路：

使用dp table方法，先判断对应位置的两个字符是否相同。

若相同取arr[i-1][j-1]的值，因为相同的话什么也不用做，直接跳过。

若不同则分别计算下面三个的值，选最小的，主要就是想得到删除、插入或替换中最小编辑的数值。

• arr[i-1][j]+1
• arr[i][j-1]+1
• arr[i-1][j-1]+1

经过循环后，能够计算出arr数组的所有值，数组最末尾的值arr[m][n]便是最小编辑数。

最短编辑距离

原文：https://www.cnblogs.com/songcubi/p/14879353.html