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

#include<stdio.h>
#include<string.h>
int main() 
{
    char str1[1001] = {0};
    char str2[1001] = {0};
    scanf("%s\n%s", &str1, &str2);
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int dp[1000][1000] = {0};
    for (int i = 0; i <= len1; i++)
        dp[0][i] = i;
    for (int i = 0; i <= len2; i++)
        dp[i][0] = i;
    int min = 0;
    for (int i = 1; i <= len2; i++)
        for (int j = 1; j <= len1; j++) 
        {
            if (str1[j - 1] == str2[i - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else 
            {
                min = dp[i - 1][j - 1] + 1;
                if (min > (dp[i][j - 1] + 1))
                    min = (dp[i][j - 1] + 1);
                if (min > (dp[i - 1][j] + 1))
                    min = (dp[i - 1][j] + 1);
                dp[i][j] = min;
            }
        }
    printf("%d", dp[len2][len1]);
    return 0;
}