题解 | #计算字符串的编辑距离#
计算字符串的编辑距离
https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314
#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;
}
