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

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

int main()
{
    char a[1000];
    char b[1000];
    int alen;

    while (scanf("%s", a) != EOF)
    {

        scanf("%s", b);
        alen = strlen(a);
        int blen = strlen(b);
        int dp[alen + 1][blen + 1];
        int i, j;

        for (i = 0; i <= alen; i++)
            dp[i][0] = i;
        for (j = 0; j <= blen; j++)
            dp[0][j] = j;
        //i,j正在匹配的字符数目 对应a[i-1] b[j-1]
        for (i = 1; i <= alen; i++)
            for (j = 1; j <= blen; j++)
            {
                if (a[i - 1] == b[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else if (a[i - 1] != b[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    dp[i][j] = dp[i][j] < dp[i - 1][j] + 1 ? dp[i][j] : dp[i - 1][j] + 1;
                    dp[i][j] = dp[i][j] < dp[i][j - 1] + 1 ? dp[i][j] : dp[i][j - 1] + 1;
                }
            }

        printf("%d\n", dp[alen][blen]);
    }

    return 0;
}