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

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

void d_p(char *str0,char *str1){
    int i,j,len0,len1;
    len0=strlen(str0);
    len1=strlen(str1);
    int dp[len0+1][len1+1];
    dp[0][0]=0;
    for(i=1;i<len0+1;i++) dp[i][0]=i;
    for(i=1;i<len1+1;i++) dp[0][i]=i;
    for(i=1;i<len0+1;i++){
        for(j=1;j<len1+1;j++){
            if(str0[i-1]==str1[j-1]) dp[i][j]=dp[i-1][j-1];
            else dp[i][j]=mix(dp[i-1][j-1]+1,dp[i][j-1]+1,dp[i-1][j]+1);
        }
    }

    printf("%d \n",dp[len0][len1]);
}

int main(void) { 
	char str0[1000],str1[1000];

	while(scanf("%s",str0)!=-1){
	    scanf("%s",str1);
	    d_p(str0,str1);
	}
	return 0;
}