首页 > 试题广场 >

计算字符串的编辑距离

[编程题]计算字符串的编辑距离

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

$\hspace{15pt}$ Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转变成另一个所需的最少单字符编辑操作次数。被允许的转变包括：
$\hspace{23pt}\bullet\,$ 对于任意一个字符串，在任意位置插入一个字符；
$\hspace{23pt}\bullet\,$ 对于任意一个字符串，删除任意一个字符；
$\hspace{23pt}\bullet\,$ 对于任意一个字符串，替换任意一个字符。

$\hspace{15pt}$ 现在，对于给定的字符串 $s$ 和 $t$ ，请计算出它们的编辑距离。

输入描述:

第一行输入一个长度为 ，仅由小写字母组成的字符串 。
第二行输入一个长度为 ，仅由小写字母组成的字符串 。

输出描述:

输出一个整数，表示  和  的编辑距离。

示例1

输入

abcdefg
abcdef

输出

说明

在这个样例中，可以选择将  末尾的  删除。当然，也可以选择在  末尾插入 。

算法知识视频讲解

terirx

#include <stdio.h>
#include <string.h>
//动态规划
int main() {
    char A[1000]={0},B[1000]={0};
    int lenA=0,lenB=0;
    scanf("%s\n%s", A, B);
    lenA = strlen(A);
    lenB = strlen(B);
    //构建一个dp表格来计算最短次数问题
    char AB[1000][1000];
    int ABnum[1001][1001]={0};
    //第0行从第1列开始放入A里面的每一个字符，第0列从第1行开始放入B里面的每一个字符
    AB[0][0] = '0';
    for(int i=1; i<strlen(A)+1; i++)
        AB[0][i] = A[i-1];
    for(int i=1; i<strlen(B)+1; i++)
        AB[i][0] = B[i-1];
    //然后填入初始的数值，也就是第1行第1列开始结尾遍历，如果是有遇到相同字符，就可以少加一次1.标志置0
    int equal=1,row=0,list=0;
    for(int i=1; i<strlen(A)+1; i++)
    {
        if(AB[1][0] == AB[0][i] && equal == 1)
        {
            equal = 0;
            row--;
        }
        ABnum[1][i] = ++row;
    }
    //类似的，填入第一列的数字
    equal = 1;
    for(int i=1; i<strlen(B)+1; i++)
    {
        if(AB[0][1] == AB[i][0] && equal == 1)
        {
            equal = 0;
            list--;
        }
        ABnum[i][1] = ++list;
    }
    //进行剩下表格的填入，检查每一次填入的表格的上方和左方的数以及左上（这个是为了检查能不能代替），填入加一以后较小的那个数，如果新的字符与表格相同的话填入左斜上方的数
    for(int i=2; i<lenB+1; i++)
    {
        for(int j=2; j<lenA+1; j++)
        {
            if(AB[0][j] == AB[i][0])
            ABnum[i][j] = ABnum[i-1][j-1];
            else
             {
                ABnum[i][j] = (ABnum[i-1][j]<ABnum[i][j-1])?(ABnum[i-1][j]+1):(ABnum[i][j-1]+1);
                ABnum[i][j] = (ABnum[i][j]<(ABnum[i-1][j-1]+1))?(ABnum[i][j]):(ABnum[i-1][j-1]+1);
             };
        }
    }
    printf("%d", ABnum[lenB][lenA]);
    return 0;
}

发表于 2024-05-29 12:04:15 回复(0)

牛客364244344号

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define N 1001

int min(int a, int b, int c)
{
    int temp;
    temp = (a < b) ? a : b;
    temp = (temp < c) ? temp : c;
    return temp;
}

int main()
{
    char a[N] = {0};
    char b[N] = {0};
    scanf("%s", a);
    scanf("%s", b);
    int lenA = strlen(a);
    int lenB = strlen(b);
    // 1.建立二维数组
    int twoArrays[lenA+1][lenB+1];
    // 2.数据初始化
    for(int i = 0; i < lenA+1; i++){
        for(int j = 0; j < lenB+1; j++){
            if(i == 0 && j != 0){
                twoArrays[i][j] = j;
            }else if(i != 0 && j == 0){
                twoArrays[i][j] = i;
            }else{
                twoArrays[i][j] = 0;
            }
        }
    }
    // 通过状态方程填补数据
    for(int i = 1; i < lenA+1; i++){
        for(int j = 1; j < lenB+1; j++){
            if(a[i-1] == b[j-1]){
                twoArrays[i][j] = twoArrays[i-1][j-1];
            }else{
                int add = twoArrays[i][j-1] + 1;    // 删除一个
                int del = twoArrays[i-1][j] + 1;    // 增加一个（增加、删除其实一样）
                int replace = twoArrays[i-1][j-1] + 1;  // 替换一个
                twoArrays[i][j] = min(add, del, replace);
            }
        }
    }
    printf("%d\n", twoArrays[lenA][lenB]);
    return 0;
}

发表于 2023-10-09 21:42:44 回复(0)

初牛小客

#include <stdio.h>
#include <string.h>

int min(int a, int b){
    return a<b? a:b;
}

int main() {
    char a[1001] = {};
    char b[1001] = {};
    int dp[1001][1001] = {0};  //dp[i][j]表示长度为i、j的字符串之间的编辑距离
    
    scanf("%s", a);
    scanf("%s", b);

    int len1 = strlen(a);
    int len2 = strlen(b);

    for(int i=1; i<=len1; i++)  //初始化dp[i][j],并将字符右移一个单位，0号位存空字符
    {
        dp[i][0] = i;           //表示由空字符串转化成长度为i的字符串所需的编辑次数
        a[len1-i+1] = a[len1-i];
    }
    for(int j=1; j<=len2; j++)
    {
        dp[0][j] = j;
        b[len2-j+1] = b[len2-j];
    }
    a[0]=b[0]=' ';

    for(int i=1; i<=len1; i++)
    {
        for(int j=1; j<=len2; j++)
        {
            /*状态转移方程为：
                1、dp[i][j] = dp[i-1][j] + 1;   //表示从a中增加一个字符
                2、dp[i][j] = dp[i][j-1] + 1;   //表示从b中增加一个字符
                3、dp[i][j] = dp[i-1][j-1] + 1; //表示a[i]替换成b[j]（a[i] != b[j]）
                4、dp[i][j] = dp[i-1][j-1]      //a[i] == b[j]，不需要替换
                取四种情况的最小值
            */
            if(a[i] == b[j])
                dp[i][j] = dp[i-1][j-1];
            else
            {
                dp[i][j] = dp[i-1][j-1] + 1;
                dp[i][j] = min(dp[i][j], dp[i-1][j] + 1);
                dp[i][j] = min(dp[i][j], dp[i][j-1]+1);
            }

        }
    }
    printf("%d", dp[len1][len2]);
    return 0;
}

发表于 2023-03-02 21:24:13 回复(0)

已注销

#include <stdio.h>
#include <string.h>
#define    N    1000
int find_min(int x,int y,int z)
{
    if(x<y)
        if(x<z)
            return x;
        else
            return z;
    else
        if(y<z)
            return y;
        else
            return z;
}
int main()
{
    char str1[N],str2[N];
    scanf("%s%s",str1,str2);
    int m=strlen(str1);
    int n=strlen(str2);
    int dp[N][N],i,j,min;
    for(i=0;i<=m;i++)
        dp[i][0]=i;
    for(j=0;j<=n;j++)
        dp[0][j]=j;
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        {
            min=find_min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]);
            if(str1[i-1]==str2[j-1])
                dp[i][j]=dp[i-1][j-1];
            else
                dp[i][j]=min+1;
        }
    }
    printf("%d\n",dp[m][n]);
    return 0;
}

发表于 2022-04-28 23:09:15 回复(0)

clv

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int min(int a,int b){
    if(a>b)    return b;
    return a;
}
int max(int a,int b){
    if(a<b)    return b;
    return a;
}
int main(){
    //实用动态规划
    char str1[502]={0};
    while(~scanf("%s",str1))
    {
        char str2[502]={0};
        //gets(str1);
        scanf("%s",str2);
        strcpy(&str1[1],&str1[0]);
        strcpy(&str2[1],&str2[0]);
        str1[0]=' ';
        str2[0]=' ';
        int n=strlen(str1);
        int m=strlen(str2);
        int d[n][m];
        d[0][0]=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(i==0||j==0){
                    d[i][j]=max(i,j);
                    continue;
                }
                if(str1[i]==str2[j]){
                    int a=d[i-1][j-1];
                    d[i][j]=a;
                    continue;
                }
                //如果对应的字符并不相等的话，有三种操作
                //第一种：修改一个字符其值等于d[i-1][j-1]+1
                //第二种：删除一个字符其值等于d[i][j-1]+1
                //第三种：增加一个字符相当于另一个字符串删除一个字符其值等于d[i-1][j]+1
                if(str1[i]!=str2[j]){
                    int a=d[i-1][j-1]+1;
                    int b=d[i][j-1]+1;
                    int c=d[i-1][j]+1;
                    d[i][j]=min(min(a,b),c);
                    continue;
                }
            }
        }
        printf("%d\n",d[n-1][m-1]);
        memset(str1,0,sizeof(char )*501);
    }
}

救命救命啊！！！！为什么这个通过不了啊，把我整自闭了...

发表于 2022-02-10 17:03:48 回复(1)

校长_

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

int main()
{
    char str1[1000] = {0};
    char str2[1000] = {0};
    int len1 = 0;
    int len2 = 0;
    int i = 0;
    while(scanf("%s%s", str1, str2) != EOF)
    {
        len1 = strlen(str1);
        len2 = strlen(str2);
        int distance[len2+1][len1+1];
        memset(distance, 0, sizeof(int)*(len1+1)*(len2+1));
        /*填充距离数组的第1行和第1列*/
        for(i=0; i<=len1; i++)
        {
            distance[0][i] = i;
        }
        for(i=0; i<=len2; i++)
        {
            distance[i][0] = i;
        }
        
        for(i=1; i<=len2; i++)
        {
            for(int j=1; j<=len1; j++)
            {
                if(str1[j-1] == str2[i-1])
                {
                    distance[i][j] = distance[i-1][j-1];
                }
                else
                {
                    distance[i][j] = ((distance[i-1][j]+1) < (distance[i][j-1]+1)) ? (distance[i-1][j]+1) : (distance[i][j-1]+1);
                    if((distance[i-1][j-1]+1) < distance[i][j])
                        distance[i][j] = distance[i-1][j-1]+1;
                    else ;
                }
            }
        }
        
        printf("%d\n", distance[len2][len1]);
    }
    
    return 0;
}

发表于 2021-08-30 22:55:42 回复(0)

80后大叔

#include<stdio.h>
#define len 500
int getmin(int a, int b, int c) {
    if(a <= b && a <= c) {
        return a;
    } else if (b <= a && b <= c) {
        return b;
    } else if (c <= a && c <= b) {
        return c;
    } else {
        return -1;
    }
}
int getLev(char a[len], char b[len]) {
    int m = strlen(a);
    int n = strlen(b);
    int cost = 0, lev[len][len] = {0};
    for(int i = 0; i <= m; i++) {
        lev[i][0] = i;
    }
    for(int j = 0; j <= n; j++) {
        lev[0][j] = j;
    }
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            if(a[i-1] == b[j-1]) {
                lev[i][j] = lev[i-1][j-1];
            } else {
                lev[i][j] = getmin(lev[i][j-1] + 1, lev[i-1][j] + 1, lev[i-1][j-1] + 1);
            }
        }
    }
    return lev[m][n];
}
int main() {
    char a[len] = {0};
    char b[len] = {0};
    while(gets(a) && gets(b)) {
        printf("%d\n", getLev(a,b));
    }
}

发表于 2021-08-17 23:18:46 回复(0)