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

// 计算编辑距离的函数
int editDistance(const char *s1, const char *s2) {
    int m = strlen(s1); // s1 的长度
    int n = strlen(s2); // s2 的长度

    // 创建二维数组 dp[m+1][n+1]
    int dp[m + 1][n + 1];

    // 初始化边界条件
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i; // 将 s1 的前 i 个字符转换为空字符串需要删除 i 次
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j; // 将空字符串转换为 s2 的前 j 个字符需要插入 j 次
    }

    // 填充动态规划表
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]; // 如果字符相同，不需要额外操作
            } else {
                int insert = dp[i][j - 1] + 1;  // 插入操作
                int delete = dp[i - 1][j] + 1;  // 删除操作
                int replace = dp[i - 1][j - 1] + 1; // 替换操作
                dp[i][j] = (insert < delete ? (insert < replace ? insert : replace) : (delete < replace ? delete : replace));
            }
        }
    }

    // 返回最终的编辑距离
    return dp[m][n];
}

int main() {
    const char *s1 = "kitten";
    const char *s2 = "sitting";

    int distance = editDistance(s1, s2);
    printf("The edit distance between '%s' and '%s' is: %d\n", s1, s2, distance);
    return 0;
}