首页 > 试题广场 >

最短编辑距离

[编程题]最短编辑距离

热度指数：272 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定两个字符串。
定义三种操作：
1.插入一个字符
2.修改一个字符
3.删除一个字符
求最少几步操作使得第一个字符串变成第二个字符串。
例如：第一个字符串lighten,第二个字符串fighting
fighten (l->f) 修改
fightin (e->i) 修改
fighting (->g) 插入
一共三步

输入描述:

第一行为一个字符串s(1<=|s|<=1000)。

第二行为一个字符串t(1<=|t|<=1000)。

(保证字符串里只含小写字母。)

输出描述:

输出s到t的最短编辑距离。

示例1

输入

lighten
fighting

输出

算法知识视频讲解

JavaScript

Songcubi

这是用js-v8写的，感觉写的好幸酸，js没有二维数组。

js要使用readline()读取单行输入，用print输出。

其实想用java写，为了练习自己的js代码能力，冲！

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]);

编辑于 2021-06-12 21:00:12 回复(0)