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

优化了一下空间

#include <string.h>

int min(int a ,int b)
{
    return ((a)>(b)?(b):(a));
}

int get_diff2(char* s1, char* s2)
{
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int *dp = (int*)malloc(sizeof(int*)*(len2+1));
    int *dp2 = (int*)malloc(sizeof(int*)*(len2+1));
    int i,j;
    int tmp1,tmp2,tmp3;
    
    if(*s1=='\0')
        return strlen(s2);
    if(*s2=='\0')
        return strlen(s1);
    
    dp[0]=0;
    for (j=1; j<=len2; j++) 
    {
        dp[j] = j;
    }

    for (i=1; i<=len1; i++)
    {
        dp2[0]=i;
        for(j=1; j<=len2; j++)
        {
            tmp1 = dp[j] +1,tmp2 = dp2[j-1]+1,tmp3 = dp[j-1];
            if(s1[i-1]!=s2[j-1]) tmp3+=1;
            dp2[j] = min(min(tmp1,tmp2),tmp3);
            
            if(j==2)
            {
                dp[0]=i;
                dp[j-1] = dp2[j-1];
            }
            else if(j>=2)
                dp[j-1] = dp2[j-1];
        }
        dp[j-1] = dp2[j-1];
        
    }
    return dp[len2];
}

int main(){
    
    char A[501];
    char B[501];
    int num;
    while(gets(A)&&gets(B))
    {
        
        num = get_diff2(A,B);
        printf("%d\n",num);
    }
    return 0;
    
}