请用c语言来解决编辑距离问题
时间: 2023-08-21 12:02:41 浏览: 40
下面是使用动态规划解决编辑距离问题的C语言代码示例:
```
#include <stdio.h>
#include <string.h>
#define MAX_LEN 1000
int min(int x, int y, int z) {
return (x < y) ? ((x < z) ? x : z) : ((y < z) ? y : z);
}
int editDistance(char *str1, char *str2, int m, int n) {
int dp[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0) {
dp[i][j] = j;
} else if (j == 0) {
dp[i][j] = i;
} else if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]);
}
}
}
return dp[m][n];
}
int main() {
char str1[MAX_LEN] = "sitting";
char str2[MAX_LEN] = "kitten";
printf("Minimum Edit Distance: %d\n", editDistance(str1, str2, strlen(str1), strlen(str2)));
return 0;
}
```
在这个例子中,我们将字符串“sitting”转换为字符串“kitten”所需的最少操作次数为2,因此输出结果为“Minimum Edit Distance: 2”。