题解 | #计算字符串的编辑距离#

#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;
}