思路:对于给定字符串,我们可以把它分成三段A B C,旁边两段是仅由lqb组成的,
中间一段是以非lqb开头和结尾组成的字符串
1 首先全由lqb组成的一定可以
2 如果B段不是回文串,修改也没用
3 如果中间是回文,则判断反过来的A段是否是C的前缀
且A的长度要小于C,因为只能在前面加
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int n=s.size();
int l=n,r=-1;//首先判断由非lqb组成的中间字符串的边界位置
for(int i=0;i<n;i++)
{
if(s[i]!='l'&&s[i]!='q'&&s[i]!='b')
{
l=min(l,i);
r=max(r,i);//保存边界位置
}
}
//cout<<l<<" "<<r<<endl;
if(r==-1)//如果全是lqb必然可以
{
puts("Yes");
continue;
}
int flag=0;
for(int i=l,j=r;i<j;i++,j--)//判断中间字符串是否是回文
{
if(s[i]!=s[j])
{
flag=1;
break;
}
}
if(flag||l>n-r-1)//如果不是回文,或者前部分长度大于后部分,就不能成功
//为什么减1,因为下标从0开始
puts("No");
else
{
int flag1=0;
for(int i=l-1,j=r+1;i>=0&&j<n;i--,j++)//判断前部分反过来是否是后部分的前缀
{
if(s[i]!=s[j])
{
flag1=1;
break;
}
}
if(flag1)
puts("No");
else puts("Yes");
}
}
}