Edit Distance
1000(ms)
65535(kb)
568 / 2526
设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的字符操作包括 (1)删除一个字符; (2)插入一个字符; (3)将一个字符改为另一个字符。 将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的2 个字符串A和B,计算出它们的编辑距离d(A,B)。
输入
第一行是字符串A,文件的第二行是字符串B。字符串长度不大于2000。
输出
输出距离d(A,B)
样例输入
fxpimu xwr
样例输出
5
题解:设dp[i][j]表示第一个字符串0-i子串与第二个字符串0-j子串的最短编辑距离
dp[0][j]:当i=0时相当于,第一个字符串为空,第二个字符串长度为j,此时相当于给第一个字符串加字符。
dp[i][0]:当j=0时相当于,第一个字符串长度为i,第二个字符串长度为0,此时相当于给第一个字符串删字符。
dp[i][j]:i>0,j>0时,有dp[i][j] = min(dp[i - 1][j]+1, min(dp[i][j - 1]+1, dp[i - 1][j - 1] + (!(str1[i-1] == str2[j-1]))));
此时对于dp[i][j]可以由dp[i - 1][j]+1(第一个字符串加一个字符),dp[i][j - 1]+1(第一个字符串删除一个字符),dp[i - 1][j - 1] +flag(第一个字符串修改一个字符)取最小得到。
#include<iostream> #include<stdio.h> #include<queue> #include<string> #include<string.h> #include<cmath> #include<algorithm> using namespace std; #define INF 0x3f3f3f3f #define LL long long int #define getl(str) strlen(str) #define M(dp,a) memset(dp,sizeof(dp),a) int dp[2005][2005]; int main() { char sa[2005], sb[2005]; while (cin >> sa >> sb) { M(dp, 0); int len1 = getl(sa); int len2 = getl(sb); for (int i = 0;i <= len1;i++) { for (int j = 0;j <= len2;j++) { if (i == 0)dp[i][j] = j; else if(j==0)dp[i][j] = i; else dp[i][j] = min(dp[i - 1][j]+1, min(dp[i][j - 1]+1, dp[i - 1][j - 1] + (!(sa[i-1] == sb[j-1])))); } } cout << dp[len1][len2] << endl; } return 0; }