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

采用动态递归的方法

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

char s1[1001] = {0};
char s2[1001] = {0};

#define MIN(a,b) (a<b?a:b)
#define MAX(a,b) (a>b?a:b)

int dp[1001][1001] = {0};

int dis_levenshtein(int i, int j) {
    int min;

    if (*(s1 + i - 1) == *(s2 + j - 1)) {
        return dp[i - 1][j - 1];
    } else 
    {
        min = MIN(MIN(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]);
        return min + 1;
    }
}


int main() {

    while (scanf("%s", s1) != EOF) {
        scanf("%s", s2);
        
        for(int i=0; i<= strlen(s1); i++){
            dp[i][0] = i;
        }
        for(int j=0; j<= strlen(s2); j++){
            dp[0][j] = j;
        }

        for (int i = 1; i <= strlen(s1); i++) {
            for (int j = 1; j <= strlen(s2); j++) {
                dp[i][j] = dis_levenshtein(i, j);
            }
        }

        printf("%d\n", dp[strlen(s1)][strlen(s2)]);
    }



    return 0;
}

以下方法便于理解，但是复杂度太高

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

char s1[1001] = {0};
char s2[1001] = {0};

#define MIN(a,b) (a<b?a:b)
#define MAX(a,b) (a>b?a:b)

int dis_levenshtein(int i, int j) {

    int len1 = strlen(s1 + i);
    int len2 = strlen(s2 + j);
    if (MIN(len1, len2) == 0) {
        return MAX(len1, len2);
    }

    if (s1[i] == s2[j]) {
        return dis_levenshtein(i + 1, j + 1);
    } else {
        int d1 = dis_levenshtein(i + 1, j); //add a char in s2
        int d2 = dis_levenshtein(i, j + 1); //delete a char in s2
        int d3 = dis_levenshtein(i + 1, j + 1); //modify a char in s2
        return MIN(MIN(d1, d2), d3) + 1;
    }
}

int main() {

    while (scanf("%s", s1) != EOF) {
        scanf("%s", s2);
        printf("%d\n", dis_levenshtein(0,0));
    }

    return 0;
}