首页给出编辑距离的C++代码

给出编辑距离的C++代码

时间: 2024-12-25 12:14:54 浏览: 41

编辑距离的C++代码通常会利用动态规划的思想，下面是一个简单的实现示例： ```cpp #include <iostream> #include <vector> int editDistance(std::string str1, std::string str2) { int m = str1.length(); int n = str2.length(); // 初始化二维数组 std::vector<std::vector<int>> dp(m+1, std::vector<int>(n+1, 0)); for (int i=1; i<=m; i++) { dp[i][0] = i; } for (int j=1; j<=n; j++) { dp[0][j] = j; } // 动态规划填充dp数组 for (int i=1; i<=m; i++) { for (int j=1; j<=n; j++) { if (str1[i-1] == str2[j-1]) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = std::min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1; } } } return dp[m][n]; // 返回最终的编辑距离 } int main() { std::string str1 = "kitten"; std::string str2 = "sitting"; int distance = editDistance(str1, str2); std::cout << "The edit distance between " << str1 << " and " << str2 << " is: " << distance << std::endl; return 0; } ``` 这个代码首先初始化一个二维数组来存储每个位置的编辑距离，然后逐个比较字符串的字符，更新对应位置的值。最后返回整个字符串的编辑距离。

阅读全文