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

再优化一点儿，最后所需空间为O(N)

#include <stdio.h>
#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;
    int dp1,dp2; //优化空间用
    
    if(*s1=='\0')
        return strlen(s2);
    if(*s2=='\0')
        return strlen(s1);
    
    for (j=0; j<=len2; j++) 
        dp[j] = j;

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

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