UNIX系统下有一个行编辑器ed，它每次只对一行文本做删除一个字符、插入一个字符或替换一个字符三种操作

UNIX系统下有一个行编辑器ed，它每次只对一行文本做删除一个字符、插入一个字符或替换一个字符三种操作。例如某一行的内容是“ABC”，经过把第二个字符替换成“D”、删除第一个字符、末尾插入一个字符“B”，这三步操作后，内容就变成了“DCB”。即“ABC”变成“DCB”需要经过3步操作，我们称它们的编辑距离为3。现在给你两个任意字符串（不包含空格），请帮忙计算它们的最短编辑距离。输入描述: 输入包含多组数据。每组数据包含两个字符串m和n，它们仅包含字母，并且长度不超过1024。输出描述: 对应每组输入，输出最短编辑距离。输入例子: ABC CBCDABC DCB 输出例子: 23

还没有评论

举报纠错

切换

1 个答案

#include #include #include using namespace std; int main(){ string str1, str2; while(cin >> str1 >> str2){ int n = str1.length(); int m = str2.length(); vector > dp(n+1); for(int i = 0; i <= n; ++i) dp[i].resize(m+1); dp[0][0] = 0; for(int i = 1; i <= n; ++i) dp[i][0] = i; for(int j = 1; j <= m; ++j) dp[0][j] = j; for(int i = 1; i <= n; ++i){ for(int j = 1; j <= m; ++j){ dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1); if(str1[i-1] == str2[j-1]) dp[i][j] = min(dp[i-1][j-1], dp[i][j]); else dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1); } } cout << dp[n][m] << endl; } return 0; }

还没有评论

切换

撰写答案

扫描后移动端查看本题

我也分享一个题目