2023第一篇博客,请听我唠叨一会: ................(此处省略999+字) 进入正题 1298:计算字符串距离
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 5688 通过数: 3009
对于两个不同的字符串,我们有一套操作方法来把他们变得相同,具体方法为:
修改一个字符(如把“a”替换为“b”);
删除一个字符(如把“traveling”变为“travelng”)。
比如对于“abcdefg”和“abcdef”两个字符串来说,我们认为可以通过增加/减少一个“g”的方式来达到目的。无论增加还是减少“g”,我们都仅仅需要一次操作。我们把这个操作所需要的次数定义为两个字符串的距离。
给定任意两个字符串,写出一个算法来计算出他们的距离。
【输入】第一行有一个整数n。表示测试数据的组数。
接下来共n行,每行两个字符串,用空格隔开,表示要计算距离的两个字符串。
字符串长度不超过1000。
【输出】针对每一组测试数据输出一个整数,值为两个字符串的距离。
【输入样例】
3 abcdefg abcdef ab ab mnklj jlknm
【输出样例】
1 0 4原题网站:http://ybt.ssoier.cn:8088/problem_show.php?pid=1298
这是个dp。 如果两个字符相等,那就继承dp[i-1][j-1],否则在
dp[i-1][j]+1
dp[i][j-1]+1
dp[i-1][j-1]+1
中取最小值
if(s1[i]==s2[j]){ dp[i][j]=dp[i-1][j-1]; } else{ dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1); }
然后加上循环,和边界的初始值等代码:
1 cin>>s1+1; 2 cin>>s2+1; 3 int len1=strlen(s1+1); 4 int len2=strlen(s2+1); 5 for(int i=1;i<=len1;i++){ 6 dp[i][0]=i; 7 } 8 for(int i=1;i<=len2;i++){ 9 dp[0][i]=i; 10 } 11 for(int i=1;i<=len1;i++){ 12 for(int j=1;j<=len2;j++){ 13 if(s1[i]==s2[j]){ 14 dp[i][j]=dp[i-1][j-1]; 15 } 16 else{ 17 dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1); 18 } 19 } 20 } 21 cout<<dp[len1][len2]<<endl;
不要以为这就可以了,这是多组数据!
完整代码如下:
#include <bits/stdc++.h> using namespace std; char s1[2020],s2[2020]; int dp[2020][2020]; int main(){ int t; cin>>t; while(t--){ memset(dp,0,sizeof(dp)); cin>>s1+1; cin>>s2+1; int len1=strlen(s1+1); int len2=strlen(s2+1); for(int i=1;i<=len1;i++){ dp[i][0]=i; } for(int i=1;i<=len2;i++){ dp[0][i]=i; } for(int i=1;i<=len1;i++){ for(int j=1;j<=len2;j++){ if(s1[i]==s2[j]){ dp[i][j]=dp[i-1][j-1]; } else{ dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1); } } } cout<<dp[len1][len2]<<endl; } return 0; }
总之,技术含量不高。
标签:int,s2,s1,cin,距离,1298,字符串,dp From: https://www.cnblogs.com/haoningdeboke-2022/p/17051351.html