- [GESP202403 四级] 相似字符串
题解(未AC专区)
- 2025-5-9 20:45:30 @
首先,在C++中有个东西叫函数。大家一定要把它用好,这道题用函数可方便了。
主函数不用说,大家自己写。我主要讲判断用的函数,先给代码:
bool tmp(string x,string y){
if(x==y)return true;
int lenA=x.size(),lenB=y.size();
if(abs(lenA-lenB)>1)return false;
if(lenA==lenB){
int diff=0;
for(int i=0;i<lenA;i++)
if(x[i]!=y[i]&&++diff>1)return false;
return diff==1;
}
int i=0,j=0,skipped = 0;
while(i<lenA && j< lenB){
if(x[i]!= y[j]){
if(++skipped >1)return false;
lenA>lenB?i++:j++;
}
else i++,j++;
}
return true;
}
这段代码需要解释的只有三目运算。true?i++:j++;
相当于:
if(true){
i++;
}
else{
j++;
}
接下来说思路。题目不是说完全相等的两个字符串也是相似字符串嘛,所以我们先判断两个字符串是否相等。确认完后,再判断两个字符串长度之差是否大于1
。因为进行操作后两个字符串之差最多不超过1
。然后在两者长度相等的条件下循环判断检查两个字符串(注意:每位对齐,例如apple
和ppale
的不相等字符有3
个)。最后利用双指针模拟出字符加减的情况。
完整代码:
#include<bits/stdc++.h>
using namespace std;
int t;
bool tmp(string x,string y){
if(x==y)return true;
int lenA=x.size(),lenB=y.size();
if(abs(lenA-lenB)>1)return false;
if(lenA==lenB){
int diff=0;
for(int i=0;i<lenA;i++)
if(x[i]!=y[i]&&++diff>1)return false;
return diff==1;
}
int i=0,j=0,skipped = 0;
while(i<lenA && j< lenB){
if(x[i]!= y[j]){
if(++skipped >1)return false;
lenA>lenB?i++:j++;
}
else i++,j++;
}
return true;
}
int main(){
scanf("%d",&t);
for(int i=1;i<=t;i++){
string a,b;
cin>>a>>b;
if(tmp(a,b)){
printf("similar\n");
}
else{
printf("not similar\n");
}
}
return 0;
}
信息
- ID
- 1575
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 88
- 已通过
- 30
- 上传者