Description

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a characterDelete a characterReplace a character

Example 1:

Input: word1 = "horse", word2 = "ros"Output: 3Explanation:horse -> rorse (replace \'h\' with \'r\')rorse -> rose (remove \'r\')rose -> ros (remove \'e\')Example 2:

Input: word1 = "intention", word2 = "execution"Output: 5Explanation:intention -> inention (remove \'t\')inention -> enention (replace \'i\' with \'e\')enention -> exention (replace \'n\' with \'x\')exention -> exection (replace \'n\' with \'c\')exection -> execution (insert \'u\')

Constraints:

0 <= word1.length, word2.length <= 500word1 and word2 consist of lowercase English letters.

Answer & Explaining

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

// 计算字符串word1和word2之间的最小Edit Distance
int minDistance(char* word1, char* word2) {
int m = strlen(word1); // 获取word1的长度
int n = strlen(word2); // 获取word2的长度

// 动态规划表，分配空间；m代表word1长度，n代表word2长度
int **dp = (int **)malloc((m + 1) * sizeof(int *));
for (int i = 0; i <= m; i++) {
dp[i] = (int *)malloc((n + 1) * sizeof(int));
}

// 初始化DP表的边界值
// 当word2为空时，word1需要删除m次
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
// 当word1为空时，word2需要插入n次
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}

// 填充DP表
for (int i = 1; i <= m; i++) { // 遍历word1的每个字符
for (int j = 1; j <= n; j++) { // 遍历word2的每个字符
if (word1[i - 1] == word2[j - 1]) {
// 当字符相同时，直接继承左上角的值
dp[i][j] = dp[i - 1][j - 1];
} else {
// 当字符不同时，取三种操作的最小值加1
dp[i][j] = 1 + fmin(fmin(dp[i - 1][j], // 删除操作
dp[i][j - 1]), // 插入操作
dp[i - 1][j - 1]); // 替换操作
}
}
}

int result = dp[m][n]; // 最终结果存储在dp[m][n]中

// 释放动态分配的内存
for (int i = 0; i <= m; i++) {
free(dp[i]);
}
free(dp);

return result; // 返回最小编辑距离
}

Testing

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

// 计算字符串word1和word2之间的最小Edit Distance
int minDistance(char* word1, char* word2) {
int m = strlen(word1); // 获取word1的长度
int n = strlen(word2); // 获取word2的长度

// 动态规划表，分配空间；m代表word1长度，n代表word2长度
int **dp = (int **)malloc((m + 1) * sizeof(int *));
for (int i = 0; i <= m; i++) {
dp[i] = (int *)malloc((n + 1) * sizeof(int));
}

// 初始化DP表的边界值
// 当word2为空时，word1需要删除m次
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
// 当word1为空时，word2需要插入n次
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}

// 填充DP表
for (int i = 1; i <= m; i++) { // 遍历word1的每个字符
for (int j = 1; j <= n; j++) { // 遍历word2的每个字符
if (word1[i - 1] == word2[j - 1]) {
// 当字符相同时，直接继承左上角的值
dp[i][j] = dp[i - 1][j - 1];
} else {
// 当字符不同时，取三种操作的最小值加1
dp[i][j] = 1 + fmin(fmin(dp[i - 1][j], // 删除操作
dp[i][j - 1]), // 插入操作
dp[i - 1][j - 1]); // 替换操作
}
}
}

int result = dp[m][n]; // 最终结果存储在dp[m][n]中

// 释放动态分配的内存
for (int i = 0; i <= m; i++) {
free(dp[i]);
}
free(dp);

return result; // 返回最小编辑距离
}

// 测试函数
int main() {
char word1[] = "horse"; // 测试字符串1
char word2[] = "ros"; // 测试字符串2
printf("Minimum Edit Distance: %d\\n", minDistance(word1, word2)); // 输出结果
return 0;
}