算法第三章 实践报告
1. 实践题目
7-3 编辑距离问题 (30 分)
设 A 和 B 是 2 个字符串. 要用最少的字符操作将字符串 A 转换为字符串 B. 这里所说的字符操作包括 (1) 删除一个字符; (2) 插入一个字符; (3) 将一个字符改为另一个字符. 将字符串 A 变换为字符串 B 所用的最少字符操作数称为字符串 A 到 B 的编辑距离, 记为 d(A,B). 对于给定的字符串 A 和字符串 B, 计算其编辑距离 d(A,B).
输入格式:
第一行是字符串 A, 文件的第二行是字符串 B.
提示: 字符串长度不超过 2000 个字符.
输出格式:
输出编辑距离 d(A,B)
输入样例:
在这里给出一组输入. 例如:
fxpimu
xwrs
输出样例:
在这里给出相应的输出. 例如:
5
2. 问题描述
设 A 和 B 是 2 个字符串. 要用最少的字符操作将字符串 A 转换为字符串 B. 这里所说的字符操作包括 (1) 删除一个字符; (2) 插入一个字符; (3) 将一个字符改为另一个字符. 将字符串 A 变换为字符串 B 所用的最少字符操作数称为字符串 A 到 B 的编辑距离, 记为 d(A,B). 对于给定的字符串 A 和字符串 B, 计算其编辑距离 d(A,B).
3. 算法描述
运用动态规划的思想, 用数组 d[i][j] 记录从 a 到 b 的编辑距离.
当 i=0 时, 表示数组 a 中有 0 个元素, 则 d[0][j]=j,
当 j=0 时, 表示数组 b 中有 0 个元素, 则 d[i][0]=i.
递归方程为 d[i][j] = d[i-1][j-1] (当 a[i-1]=b[j-1] 时),
- D[i][j] = min{
- d[i-1][j-1]+1,d[i][j-1]+1,d[i-1][j]+1
- }
- (当 a[i-1]!=b[j-1] 时)
min 中的三项依此对应修改, 插入和删除三种操作.
部分代码:
- int lena = strlen(a);
- int lenb = strlen(b);
- for(int i=0;i<=lena;i++){
- d[i][0] = i;
- }
- for(int i=0;i<=lenb;i++){
- d[0][i] = i;
- }
- for(int j=1;j<lenb+1;j++){
- for(int i=1;i<lena+1;i++){
- if(a[i-1]==b[j-1]) {
- d[i][j] = d[i-1][j-1];
- }
- else {
- d[i][j] = min(d[i-1][j-1]+1,d[i][j-1]+1,d[i-1][j]+1);
- }
- }
- }
- cout<<d[lena][lenb];
4. 算法时间及空间复杂度分析 (要有分析过程)
因为有两重循环, 所以算法的时间复杂度为 O(lena*lenb)
开设了一个二维数组, 所以算法的空间复杂度为 O(lena*lenb)
5. 心得体会 (对本次实践收获及疑惑进行总结)
在本次实践中, 再次运用了动态规划的思想, 最后发现这道题的算法和求解最长公共子序列的算法有相似之处. 只不过最长公共子序列是从两字符串的后面开始比较, 而这道题从两字符串的开头开始比较, 比较有利于填写 d[i][j]. 同时在编写程序的过程中, 一开始没有注意数组下标这方面的细节所以导致了运行出错, 后来通过具体的例子, 画出对应的编辑距离的二维数组, 这样才把下标使用对了.
来源: http://www.bubuko.com/infodetail-2842880.html