【十二题解】 | #计算字符串的编辑距离#

这里要注意的一个点就是创建dp数组的时候，行和列都需要多一个，因为dp[0][0]的含义是两个单词都只有0个的时候需要编辑的次数，所以比如说某个单词有七个，初始化dp数组的时候我只给七个，0会占去一个所以只有六个字母会被比较

#include<stdio.h>

int f_min(int a, int b, int c){

int min;
if(a>b){
    min=b;
}
else{
    min =a;
}
if(min>c)min=c;
return min;

}

int main(){

char first[1000]={0};
char second[1000]={0};
while(scanf("%s", first) != EOF){
    scanf("%s", second);
    int i, j;
    for(i=0; first[i] != '\0'; i++);
    for(j=0; second[j] != '\0'; j++);
    int**dp=(int**)malloc(sizeof(int*)*(i+1));
    for(int x=0; x<i+1; x++){
        dp[x]=(int*)malloc(sizeof(int)*(j+1));
    }//dp[x][0]=x  dp[0][j]=0
    for(int x=0; x<i+1; x++)dp[x][0]=x;
    for(int x=0; x<j+1; x++)dp[0][x]=x;

    for(int m=1; m<=i; m++)
    {
        for(int n=1; n<=j; n++){
            if(first[m-1]==second[n-1]){
                dp[m][n]=dp[m-1][n-1];
            }
            else{
                dp[m][n]=f_min(dp[m-1][n]+1, dp[m][n-1]+1, dp[m-1][n-1]+1);
            }
        }
    }
    printf("%d\n", dp[i][j]);
}

}