首页 > 试题广场 >

最短编辑距离

[编程题]最短编辑距离

热度指数：273 时间限制：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

输出

算法知识视频讲解

自律

这个题目就是动态规划

记dp[i][j] 表示i和j相等所需要的修改次数

那么当a[i] == b[j] 时 dp[i][j]= dp[i - 1][j - 1];

当两者不相等的时候考虑修改的三种情况

1. 把第i位删除掉那么说明第i - 1位和第j位是相等的有：dp[i][j] = min(dp[i - 1][j] + 1,dp[i][j]);；

2.在第i位前面增加一个数那么说明第i位是和第j - 1位相等的有：dp[i][j] = min(dp[i][j - 1] + 1,dp[i][j]);

3.修改第i位，那么这个就很简单了说明第i - 1和第j - 1是相等的有：dp[i][j] = min(dp[i - 1][j - 1] + 1,dp[i][j]);

注意对于dp初始化的时候要初始化dp[i][0] = i dp[j][0] = j;

#include <bits/stdc++.h>
 
using namespace std;
 
const int inf = 0x3f3f3f3f;
 
char a[1010],b[1010];
 
int dp[1010][1010]; // a is i pos  b is j pos 
 
int main()
{
    int n;
    scanf("%s", a + 1);
    int m;
    scanf("%s", b + 1);
    n = strlen(a + 1);
    m = strlen(b + 1);
    for(int i = 0; i <= m; i++) dp[0][i] = i;
    for(int i = 0; i <= n; i++) dp[i][0] = i;
    for(int i = 1; i <= n; i++)
    {
        //dp[i][j] = inf;
        for(int j = 1; j <= m; j++)
        {
            dp[i][j] = inf;
            if(a[i] == b[j])
            {
                dp[i][j]= dp[i - 1][j - 1]; 
            }
            else
            {
                dp[i][j] = min(dp[i - 1][j] + 1,dp[i][j]); // 删除 都是对于第i位来看的
                dp[i][j] = min(dp[i][j - 1] + 1,dp[i][j]); // 增加
                dp[i][j] = min(dp[i - 1][j - 1] + 1,dp[i][j]); // 修改 啊难受呀老弟
            }
            //cout<<dp[i][j]<<endl;
        }
    }
    printf("%d\n",dp[n][m]);
    return 0;
}

发表于 2019-09-03 17:14:21 回复(0)

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)

{球球offer}

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int mymin(int a, int b) {
	return a < b ? a : b;
}
int main() {
	string s, t;
	getline(cin, s);
	getline(cin, t);
	int lens = s.size();
	int lent = t.size();
	vector<vector<int>>arr(lens + 1, vector<int>(lent + 1, 0));
	for (int i = 0; i <= lens; i++) {
		arr[i][0] = i;
	}
	for (int i = 1; i <= lent; i++) {
		arr[0][i] = i;
	}

	for (int i = 1; i <= lens; i++) {
		for (int j = 1; j <= lent; j++) {
			if (s[i - 1] == t[j - 1]) {
                                //分别对应不动、删、增
				arr[i][j] = mymin(arr[i - 1][j - 1], mymin(arr[i][j - 1] + 1, arr[i - 1][j] + 1));
			}
			else {
                                //分别对应改、删、增
				arr[i][j] = mymin(arr[i - 1][j - 1]+1, mymin(arr[i][j - 1] + 1, arr[i - 1][j] + 1));
			}
		}
	}
	cout << arr[lens][lent];

	system("pause");
	return 0;
}

编辑于 2019-09-10 01:07:13 回复(0)