题目
题目描述
????????编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
例如将kitten一字转成sitting：
步骤1：sitten （k->s）??? 步骤2：sittin （e->i）??? 步骤3：sitting （->g）
????????所以kitten和sitting的编辑距离是3。俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。
????????给出两个字符串a,b，求a和b的编辑距离。
输入
第1行：字符串a(a的长度 <= 1000)。 第2行：字符串b(b的长度 <= 1000)。
输出
输出a和b的编辑距离。
样例输入
kitten
sitting
样例输出
3
题目大意
? ? ? ? 给你两个字符串s,t要你求至少删除、加入、替换多少次后s变为t。
算法
? ? ? ? 这道题用动态规划。
? ? ? ? 与其说是s转化到t，不如说是s和t的相互匹配。我们设f[i][j]表示s[1~i]与匹配t[1~j]的最小步数。
????????有两种情况：
1.s[i]与t[j]一样，则得到状态转移方程
if (s[i]==t[j]) f[i][j]=f[i-1][j-1];
2.否则，要通过删除、加入、替换把s[i]变成t[j]，我们就其取最小值，得到状态转移方程：
else f[i][j]=min{f[i-1][j]+1,f[i-1][j-1]+1,f[i][j-1]+1};
代码
#include <cstdio>
#include <cstring>
using namespace std;
int min(int a,int b);
const int N=3005;
char s[N],t[N];
int f[N][N];
int main()
{
int n,m;
scanf("%s",s+1);
scanf("%s",t+1);
n=strlen(s+1),m=strlen(t+1);
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
{
if (s[i]==t[j]) f[i][j]=f[i-1][j-1];
else f[i][j]=min(f[i-1][j]+1,min(f[i-1][j-1]+1,f[i][j-1]+1));
}
printf("%d",f[n][m]);
return 0;
}
int min(int a,int b)
{
if (a<b) return a;
else return b;
}
?
|