chatgpt最小编辑距离

最小编辑距离（Minimum Edit Distance）是指将一个字符串转换为另一个字符串所需的最少编辑操作次数。编辑操作包括插入一个字符、删除一个字符和替换一个字符。

以下是一个使用动态规划算法实现最小编辑距离的示例代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int minEditDistance(const std::string& word1, const std::string& word2) {
    int m = word1.length();
    int n = word2.length();

    // 创建一个二维数组来存储最小编辑距离
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    // 初始化边界条件
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;
    }

    // 动态规划计算最小编辑距离
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = std::min({ dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1 });
            }
        }
    }

    return dp[m][n];
}

int main() {
    std::string word1 = "kitten";
    std::string word2 = "sitting";

    int distance = minEditDistance(word1, word2);

    std::cout << "The minimum edit distance between \"" << word1 << "\" and \"" << word2 << "\" is: " << distance << std::endl;

    return 0;
}

在这个示例中，我们定义了一个minEditDistance函数，它接受两个字符串word1和word2作为参数，并返回它们之间的最小编辑距离。

在main函数中，我们定义了两个字符串word1和word2，分别为"kitten"和"sitting"。然后我们调用minEditDistance函数来计算最小编辑距离，并输出结果。

输出结果为：The minimum edit distance between "kitten" and "sitting" is: 3

这表示将字符串"kitten"转换为"sitting"所需的最少编辑操作次数为3。

希望对你有帮助！

pengdu/最小编辑距离.md