文章
5
粉丝
221
获赞
12
访问
25.4k
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1005;
int dp[MAX][MAX];
string a,b;
//dp[i][j]是指字符串1中的前i个字符和字符串2中的前j个字符的编辑距离
int main(){
cin>>a>>b;
int lena = a.length();
int lenb = b.length();
memset(dp, 0, sizeof(dp));
//initialization
for(int i=0;i<lena;i++) dp[i][0]=i;
for(int i=0;i<lenb;i++) dp[0][i]=i;
//套公式
int t1=0, t2=0;
//注意代码中的两层循环时从1开始的,从而使得i-1和j-1不需要特殊处理
for(int i=1;i<=lena;i++){
for(int j=1;j<lenb;j++){
t1 = 1 + min(dp[i][j-1], dp[i-1][j]);
if(a[i-1]==b[j-1]) t2 = dp[i-1][j-1];
else t2 = dp[i-1][j-1] + 1;
dp[i][j] = min(t1,t2);
}
}
cout<<dp[lena-1][lenb-1]<<endl;
return 0;
}
登录后发布评论
暂无评论,来抢沙发