首先,在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。然后在两者长度相等的条件下循环判断检查两个字符串(注意:每位对齐,例如appleppale的不相等字符有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;
}

1 条评论

  • 1

信息

ID
1575
时间
1000ms
内存
256MiB
难度
6
标签
递交数
88
已通过
30
上传者