最短编辑距离
题目描述
给定两个字符串A 和 B,现在要将A经过若干操作变为B,可进行的操作有
1.删除(将字符串A中的某个字符删除)
2.插入(在字符串A的某个位置插入某个字符)
3.替换(将字符串A中的某个字符替换成另外一个字符)
现在请求出,将A变为B至少需要进行多少次操作。(字符串中均只包含小写字母)
输入格式
第一行包含整数n,表示字符串A的长度。
第二行包含一个长度为n的字符串A。
第三行包含整数m,表示字符串B的长度。
第四行包含一个长度为m的字符串B。
字符串中均只包含小写字母。
输出格式
输出一个整数,表示最少操作次数。
样例
数据范围
1≤n,m≤1000
输入样例:
10
AGTCTGACGC
11
AGTAAGTAGGC
输出样例:
4
分析
算法
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main() {
scanf("%d%s", &n, a + 1); //字符串下标从1开始(当状态转移方程里面涉及到 i - 1,下标从1开始比较好)
scanf("%d%s", &m, b + 1); // 下面是初始化边界
for (int i = 0; i <= m; i++) f[0][i] = i; // 当A有0个字母,A的前0个字母想匹配B的前i个字母,只能用“添加”操作i次(操作次数与B的长度有关)
for (int i = 0; i <= n; i++) f[i][0] = i; // A 的前i个字母与B的前0个匹配,删除操作进行 i 次
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if (a[i] == b[j])
f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else
f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}
printf("%d\n",f[n][m]); // 把A的前n个字母变成B的前m个字母
return 0;
// 上面的for for if else 可以用下面的方式合并
// for (int i = 1; i <= n; i++)
// for (int j = 1; j <= m; j++)
// f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1; f[i - 1][j - 1] + (a[i] != b[j]));
// }
时间复杂度
状态数量 n^2个,计算每个状态需要3次运算 ==> 3n^2 O(n^2).