题解 | #计算字符串的编辑距离#
计算字符串的编辑距离
https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314
同样经典的一道动态规划题目
主要是dp数组的计算
可以参考https://blog.csdn.net/tianjindong0804/article/details/115803158
#include<stdio.h>
#include<string.h>
int main(void)
{
char str1[1001]={0};
char str2[1001]={0};
scanf("%s%s",&str1,&str2);
int len1=strlen(str1);
int len2=strlen(str2);
int dp[1002][1002]={0};
//初始化dp数组
for(int i=0;i<=len1;i++)
{
dp[0][i]=i;
}
for(int i=0;i<=len2;i++)
{
dp[i][0]=i;
}
//开始计算dp数组
int min=0;
for(int i=1;i<=len2;i++)
{
for(int j=1;j<=len1;j++)
{
//此处是str1[j-1]和str2[i-1],易错，因为dp数组的行列宽度都比str大1
if(str1[j-1]==str2[i-1]){dp[i][j]=dp[i-1][j-1];}
else
{
min=dp[i-1][j-1]+1;
if(min>(dp[i][j-1]+1)){min=(dp[i][j-1]+1);}
if(min>(dp[i-1][j]+1)){min=(dp[i-1][j]+1);}
dp[i][j]=min;
}
}
}
printf("%d",dp[len2][len1]);
return 0;
}
查看13道真题和解析