问题描述:
两个字符串, 一个是起点字符串, 另一个是终点.
例如, 起点字符串 ddl 到终点字符串 de 的转换步骤如下:
ddl->del->def.
编辑距离为 2.
算法分析:
首先考虑上面例子中 ddl 的第一个字符和 def 的第一个字符, 它们是一样的, 所以只需要计算 a[2...lengthA]和 b[2...lengthB](dl 和 ef)之间的距离即可.
若两个字符串的第一个字符不同, 例如 adl 和 def, 可以三选一:
把终点串的第一个字符插入到起点串的第一个字符之前 (adl->dadl), 然后计算 a[1...lengthA] 和 b[2...lengthB](dadl 和 def)的距离即可;
删除起点串的第一个字符 (adl->dl), 然后计算 a[2...lengthA] 和 b[1...lengthB](dl->def)的距离即可;
修改起点串的第一个字符成终点串的第一个字符 (adl->ddl), 然后计算 a[2...lengthA] 和 b[2...lengthB](dl 和 ef)的距离即可.
考虑起点串的第 i 个字符和终点串的第 j 个字符的话也是一样的.
当不考虑起点串的前 i-1 字符和终点串的前 j-1 个字符, 如果起点串的第 i 个字符和终点串的第 j 个字符相等, 即 a[i-1] = b[j-1], 则只需要计算 a[i...lengthA]和 b[j...lengthB]之间的距离即可.
如果不相等, 可以三选一:
把终点串的第 j 个字符插入到起点串的第 i 个字符之前, 然后计算 a[i...lengthA]和 b[j+1...lengthB]的距离即可;
删除起点串的第 i 个字符, 然后计算 a[i+1...lengthA]和 b[j...lengthB]的距离即可;
修改起点串的第 i 个字符成终点串的第 j 个字符, 之然后计算 a[i+1...lengthA]和 b[j+1...lengthB]的距离即可;
那么进行三选一的依据是什么呢? 是起点串的前 i-1 字符和终点串的前 j-1 个字符的编辑距离.
递归方程:
edit[i-1][j]+1 相当于给起点串的最后插入了终点串的最后的字符, 插入操作使得 edit+1, 之后计算 edit[i-1][j];
edit[i][j-1]+1 相当于将起点串的最后字符删除, 删除操作 edit+1, 之后计算 edit[i][j-1];
edit[i-1][j-1]+flag 相当于通过将起点串的最后一个字符替换为终点串的最后一个字符. 若 a[i-1] = b[j-1],flag = 0; 若 a[i-1] != b[j-1],flag = 1.
- #include<iostream>
- #include<string.h>
- using namespace std;
- int main() {
- char a[2000], b[2000];
- cin.getline((a+1), 2001);
- cin.getline((b+1), 2001);
- int lengthA = strlen(a) - 1;
- int lengthB = strlen(b) - 1 ;
- int editDistance[2001][2001];
- editDistance[0][0] = 0;
- for(int i = 1; i <= lengthA; i++) {
- editDistance[i][0] = i;
- }
- for(int i = 1; i <= lengthB; i++) {
- editDistance[0][i] = i;
- }
- for(int i = 1; i <= lengthA; i++)
- for(int j = 1; j <= lengthB; j++) {
- if(a[i] == b[j]) {
- editDistance[i][j] = editDistance[i-1][j-1];
- }
- else {
- editDistance[i][j] = min(editDistance[i-1][j], min(editDistance[i][j-1], editDistance[i-1][j-1])) + 1;
- }
- }
- cout << editDistance[lengthA][lengthB];
- return 0;
- }
- View Code
复杂度分析
时间复杂度: O(m*n)
空间复杂度: O(1)
心得
递归方程很重要.
来源: http://www.bubuko.com/infodetail-3251628.html