编辑距离问题c++
时间: 2023-08-03 12:21:20 浏览: 53
编辑距离问题是指将一个字符串转换成另一个字符串所需的最少操作次数,包括插入、删除和替换字符。下面是使用动态规划解决编辑距离问题的C++代码示例:
```
#include <iostream>
#include <cstring>
using namespace std;
int min(int x, int y, int z) {
return min(min(x, y), z);
}
int editDistance(string str1, string str2, int m, int n) {
int dp[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0) {
dp[i][j] = j;
} else if (j == 0) {
dp[i][j] = i;
} else if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]);
}
}
}
return dp[m][n];
}
int main() {
string str1 = "sitting";
string str2 = "kitten";
cout << "Minimum Edit Distance: " << editDistance(str1, str2, str1.length(), str2.length()) << endl;
return 0;
}
```
在这个例子中,我们将字符串“sitting”转换为字符串“kitten”所需的最少操作次数为2,因此输出结果为“Minimum Edit Distance: 2”。