编辑距离
题目描述
设 \(A\) 和 \(B\) 是两个字符串。我们要用最少的字符操作次数,将字符串 \(A\) 转换为字符串 \(B\)。这里所说的字符操作共有三种:
- 删除一个字符;
- 插入一个字符;
- 将一个字符改为另一个字符。
\(A, B\) 均只包含小写字母。
输入格式
第一行为字符串 \(A\);第二行为字符串 \(B\);字符串 \(A, B\) 的长度均小于 \(2000\)。
输出格式
只有一个正整数,为最少字符操作次数。
样例 #1
样例输入 #1
sfdqxbw
gfdgw
样例输出 #1
4
提示
对于 \(100 \%\) 的数据,\(1 \le |A|, |B| \le 2000\)。
最近遇到了很多类似这样的题,所以把这些题整理在一起。刚开始我以为这个黄题,可以使用贪心模拟来做,但是贪心是错的,我们来DP考虑
对于修改操作而言,非常好做,因为它不会改变字符串的长度
对于插入和删除操作,插入会增加长度,删除操作会减少长度,对于这样的DP,我们会设定\(dp[i][j]表示将A串前i个位置变成B串前j个位置的最少编辑距离是多少?\)刚开始的想法是,如果我们在A串第i个位置插入字符串之后,A串的i+1个位置就变化了,这怎么DP呢?
做这种题的宗旨是无论插入、删除操作,我们不要让它影响原来的位置关系
对于这道题而言,假设\(a[i]==b[j],那么f[i][j]=f[i-1][j-1],如果a[i]!=b[j]呢,我们需要进行插入和删除操作,如果我们进行插入操作,那么b[j]就要和插入的字符匹配,a[i]和b[j-1]进行匹配,f[i][j]=f[i][j-1]+1,如果我们进行的是删除操作呢,b[j]和a[i-1]就匹配好了,所以f[i][j]=f[i-1][j]+1,如果是修改操作的话,就更简单了,f[i][j]=f[i-1][j-1]+1,这个题就做完了\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
char s[2005],t[2005];
int f[2005][2005];
int main(){
scanf("%s%s",s+1,t+1);
int n=strlen(s+1);
int m=strlen(t+1);
memset(f,0x3f,sizeof f);
f[0][0]=0;//边界,假设只有一个字符
for(int i=1;i<=n;i++)
f[i][0]=i;// 需要进行i次删除操作
for(int i=1;i<=m;i++)
f[0][i]=i;// 需要进行i次添加操作
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,f[i][j-1]+1);
f[i][j]=min(f[i][j],f[i-1][j-1]+1);
}
}
cout<<f[n][m]<<endl;
return 0;
}