蓝桥杯 回文字符串

问题描述

小蓝最近迷上了回文字符串，他有一个只包含小写字母的字符串S，小蓝可以往字符串S的开头处加入任意数目个指定字符：l、q、b（它们的 ASCII 码分别为：108、113、98）。

小蓝想要知道他是否能通过这种方式把字符串S转化为一个回文字符串。

样例输入

3 gmgqlq pdlbll aaa

样例输出

Yes No Yes

样例说明

• 对于gmgqlq，可以在前面加上qlq，使其变为回文字符串：qlqgmgqlq。
• 对于pdlbll，无法转化为回文字符串。
• 对于aaa，本身就是一个回文字符串。

评测用例规模与约定

• 对于 50% 的评测用例，1 ≤ |S| ≤ 1000，其中|S|表示字符串S的长度；
• 对于所有评测用例，1 ≤ T ≤ 10，1 ≤ Σ|S| ≤ 10^6，即所有字符串的总长度不超过 10^6。

c++代码

#include<bits/stdc++.h>usingnamespacestd;intT;string s;boolishui(string str){intleft=0,right=str.size()-1;while(right>left){if(str[left]!=str[right])returnfalse;left++;right--;}returntrue;}intmain(){cin>>T;while(T--){cin>>s;while(true){if(ishui(s)){cout<<"Yes"<<endl;break;}if(!(s.back()=='q'||s.back()=='l'||s.back()=='b')){cout<<"No"<<endl;break;}s.erase(s.size()-1);}}}//by wqs

思路解析

实在没想到，这道题目暴力也能过

我还在想怎么优化，结果直接满分了。

就是不断判断是不是回文

如果是回文输出YES

如果不是

看字符串的末尾，

如果不是qlb，直接输出No

如果是q,l,b说明可以在前面加q,l,b使得它有可能回文，我只要判断中间这一段是否回文就行，所以我把末尾这一个删除，判断下一个字符串是不是回文。例如字符串pdlbll，最后一个字符串是l,我可以变成lpdlbll,我只要判断pdlbl是不是回文，接着我可以变成lpdlbl,我只要判断pdlb是不是回文，以此类推。