门户网站开发维护合同,国内永久免费crm系统app,wordpress分类信息模板,网站后台 行间距调整题干#xff1a;
自从 Applese 学会了字符串之后#xff0c;精通各种字符串算法#xff0c;比如……判断一个字符串是不是回文串。 这样的题目未免让它觉得太无聊#xff0c;于是它想到了一个新的问题。 如何判断一个字符串在任意位置(包括最前面和最后面)插入一个字符后…题干
自从 Applese 学会了字符串之后精通各种字符串算法比如……判断一个字符串是不是回文串。 这样的题目未免让它觉得太无聊于是它想到了一个新的问题。 如何判断一个字符串在任意位置(包括最前面和最后面)插入一个字符后能不能构成一个回文串
输入描述:
仅一行为一个由字母和数字组成的字符串 s。
输出描述:
如果在插入一个字符之后可以构成回文串则输出Yes, 否则输出No。
示例1
输入
复制
applese
输出
复制
No
示例2
输入
复制
java
输出
复制
Yes
备注:
|s|≤105
题目大意 一句话题意给定一个字符串,问是否能通过添加一个字母将其变为回文串。
解题报告 可以认为插入和删除是等价的操作。想到这一点这题就会好做很多。 如果这个串本身就是回文串答案一定是Yes。因为如果原来是奇数个字符那直接加一个中间的字符就行了如果原来是偶数个字符在中间随便加一个字符依旧是回文串。 否则我们只需要找到串中对称的位置第一对 不相等的两个字符分别尝试把它们删掉后判断一下是不是回文的就行了。
时间复杂度O(n)。还有中n^2的做法就是枚举每一个删除的位置看删除之后剩下的字符串是否是回文串但是效率就太低了。。
AC代码O(n)的解法
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
bool ok(string s)
{string s2s;reverse(s2.begin(),s2.end());return ss2;
}
string str;
int main()
{bool flag 0;cinstr;int len str.size(),i;for(i 0; ilen/2;i) {if(str[i] ! str[len-1-i]) break;}if(i len/2) flag 1;if(ok(str.substr(i1,len-2*i-1))) flag 1;if(ok(str.substr(i,len-2*i-1))) flag 1;if(flag) puts(Yes);else puts(No); return 0;
}
TLE代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
bool ok(string s)
{string s2s;reverse(s2.begin(),s2.end());return ss2;
}
string str;
int main()
{ cinstr;bool flag0;int len str.size();for(int i0;ilen;i){if(ok(str.substr(0,i)str.substr(i1,len-1-i))){flag1;break;}}if(flag) puts(Yes);else puts(No);return 0;
}
一段有待考察的代码
//#includecstdio
//#includeiostream
//#includealgorithm
//#includequeue
//#includemap
//#includevector
//#includeset
//#includestring
//#includecmath
//#includecstring
//#define ll long long
//#define pb push_back
//#define pm make_pair
//#define fi first
//#define se second
//using namespace std;
//const int MAX 2e5 5;
//char s1[MAX],s2[MAX],s3[MAX],s4[MAX],c2[MAX],ch;
//int main()
//{
// cins1;
// int len strlen(s1);
// strcpy(s2,s1);
// reverse(s2,s2len);
// strcpy(c2,s2);
// for(int i 0; ilen; i) {
// if(s1[i] s2[i]) continue;
// ch s1[i];
// for(int j len; ji1; j--) c2[j] c2[j-1];
// c2[i] ch;
// break;
// }
// strcpy(s3,c2);
// strcpy(s4,s3);
// reverse(s4,s4strlen(s3));
// if(strcmp(s3,s4) 0) puts(Yes);
// else puts(No);
// return 0 ;
// }扩展一个思路给定一个字符串问添加几个字符可以构成回文串 先把原字符串逆序然后计算两字符串的最长公共子序列长度最后diff字符串长度-最长公共子序列长度diff即为如果可以形成回文串原字符串需要添加的字符个数。用到这个题目里如果diff1即可。时间复杂度O(n^2)。
