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

递归，超时了

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

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

int min(a,b,c)
{
    a = a<b?a:b;
    return a<c?a:c;
}
int mindistance(char *a, char *b)
{
    if(strlen(a) == 0 || strlen(b) == 0){//删除剩余字符
        return max(strlen(a), strlen(b)); 
    }
    if(a[strlen(a)-1] == b[strlen(b)-1]){//最后一个字符相等，比较下一个字符
        a[strlen(a)-1] = '\0';
        b[strlen(b)-1] = '\0';
        return mindistance(a, b); 
    }

   //执行删除 插入 替换
    char *a1 = (char *)malloc(strlen(a)+1);
    char *b1 = (char *)malloc(strlen(b)+1);
    memcpy(a1, a, strlen(a)+1);
    memcpy(b1, b, strlen(b)+1);
    int m,n,k;

    //删除
    a1[strlen(a1)-1] = '\0';
    m = mindistance(a1, b1); 

    //插入
    memcpy(a1, a, strlen(a)+1);
    b1[strlen(b1)-1] = '\0';
    n = mindistance(a1, b1);

    //替换
    memcpy(a1, a, strlen(a)+1);
    memcpy(b1, b, strlen(b)+1);
    a1[strlen(a1)-1] = '\0';
    b1[strlen(b1)-1] = '\0';
    k = mindistance(a1, b1);

    free(a1);
    free(b1);
    return 1 + min(m,n,k);    
}
int main(void)
{
    char a[1024];
    char b[1024];
    scanf("%s", a);
    scanf("%s", b);

    printf("%d", mindistance(a, b));

    return 0;
}