题解 | #计算字符串的编辑距离#
计算字符串的编辑距离
https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314
#include <stdio.h>
#include <string.h>
int mix(int a,int b,int c)
{
a=a<b?a:b;
a=a<c?a:c;
return a;
}
int main() {
char str1[1001],str2[1001];
scanf("%s%s",str1,str2);
int len1=strlen(str1);
int len2=strlen(str2);
int i,j;
int dp[len1+1][len2+1];
for(i=0;i<len1+1;i++)
{
for(j=0;j<len2+1;j++)
{
if(i==0&&j!=0)
{
dp[i][j]=j;
}else if(i!=0&&j==0)
{
dp[i][j]=i;
}else if(i==0&&j==0)
{
dp[i][j]=0;
}
}
}
for(i=1;i<len1+1;i++)
{
for(j=1;j<len2+1;j++)
{
if(str1[i-1]==str2[j-1])
{
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j]=mix(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1);
}
}
}
int ret=dp[len1][len2];
printf("%d\n",ret);
return 0;
}
投递字节跳动等公司10个岗位
上次被挂了后我连简历都不刷了
