题目描述
京京和东东是好朋友。东东很喜欢回文。回文是指从前往后读和从后往前读是一样的词语。京京准备给东东一个惊喜,先取定一个字符串s,然后在后面附上0个或者更多个字母形成回文,京京希望这个回文越短越好。请帮助京京计算他能够得到的最短的回文长度。
输入描述:
输入包括一个字符串s,字符串s长度length(1 ≤ length ≤ 50)
输出描述:
输出一个整数,表示牛牛能够得到的最短的回文长度。
示例1
输入
abab
输出
5
这道题目比较简单,直接找出从头到尾的最长子串长度,在处理即可,有一点贪心的思想。由于数据量比较小,可以直接用O(N^2)的算法
#include <iostream>#include <string>using namespace std;bool isPalindrome(string &str, int start, int end){while(start<end){if(str[start++]!=str[end--])return false;}return true;}int main(){string str;cin>>str;int res= str.size()-1;for(int i=0;i<str.size()-1;i++){if(isPalindrome(str,i,str.size()-1)){res = i;break;}}cout<<str.size()+res<<endl;}
如果觉得《京东校招笔试题回文》对你有帮助,请点赞、收藏,并留下你的观点哦!