题目
Description
假设字符串的基本操作仅为:删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。
我们把进行了一次上述三种操作的任意一种操作称为进行了一步字符基本操作。
下面我们定义两个字符串的编辑距离:对于两个字符串a和b,通过上述的基本操作,我们可以把a变成b或b变成a,那么字符串a变成字符串b需要的最少基本字符操作步数称为字符串a和字符串b的编辑距离。
例如:a="ABC",b="CBCD",则a与b的编辑距离为2。
你的任务就是:编一个快速的程序来计算任意两个字符串的编辑距离。Input
输入包含多组测试数据。每组测试数据一行,为字符串A和字符串B。
字符串的长度不大于1024,且全为字母。Output
编辑距离。
Sample Input
ABC CBCD
Sample Output
2
题解
数据包括两个字符串,类似于最长公共子序列的形式
可以类似的使用一个二维的 dp[i][j]
来表示字符串 a
的前 i
个字符和字符串 b
的前 j
个字符的最短编辑距离
当我们计算 dp[i][j]
时,显然我们已经有了 dp[i][j-1]
、 dp[i-1][j]
、 dp[i-1][j-1]
- 如果
a[i] == b[j]
(对应的字符相等),则加上这两个字符,对答案无影响
也即dp[i][j] = dp[i-1][j-1]
同时,也可以是a
或b
少一个字符的情况下增加一个字符,即dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + 1
- 如果
a[i] != b[j]
(对应的字符不同),则需要进行修改操作
有3种修改方式:- 修改字符:将其中一个字符变成另一个字符
即dp[i][j] = dp[i-1][j-1] + 1
- 增删字符(a):将字符串
a
的字符删掉
可以理解为:字符串a
少一个字符时,加上b
对应的字符
即dp[i][j] = dp[i-1][j] + 1
- 增删字符(a):将字符串
b
的字符删掉
可以理解为:字符串b
少一个字符时,加上a
对应的字符
即dp[i][j] = dp[i][j-1] + 1
- 修改字符:将其中一个字符变成另一个字符
同时如果两个字符的长度差为 delta
则编辑距离最少为 delta
注意好边界值即可
一开始迷之TLE,即使AC了也无法理解
代码
/* By:OhYee Github:OhYee HomePage:http://www.oyohyee.com Email:oyohyee@oyohyee.com かしこいかわいい? エリーチカ! 要写出来Хорошо的代码哦~ */ #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <vector> #include <list> #include <queue> #include <stack> #include <map> #include <set> using namespace std; typedef unsigned int LL; const int maxn = 1050; char a[maxn],b[maxn]; LL dp[maxn][maxn]; bool Do() { if(scanf("%s%s",a,b) == EOF) return false; LL lena = strlen(a); LL lenb = strlen(b); for(unsigned int i = 1;i <= lena;i++) for(unsigned int j = 1;j <= lenb;j++) { int ita = i - 1; int itb = j - 1; LL delta = (i > j) ? (i - j) : (j - i); LL Min = min(dp[i][j - 1],dp[i - 1][j]) + 1; if(a[ita] == b[itb]) { dp[i][j] = min(dp[i - 1][j - 1],Min); } else { dp[i][j] = min(dp[i - 1][j - 1] + 1,Min); } dp[i][j] = max(dp[i][j],delta); } printf("%u\n",dp[lena][lenb]); return true; } int main() { dp[0][0] = 0; for(int i = 1;i < maxn;i++) dp[0][i]=dp[i][0] = i; while(Do()); return 0; }