Description

72. Edit Distance

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 character
Delete a character
Replace a character

Example 1:

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

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
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 <= 500
word1 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;
}