【题目】
所谓回文,就是正序和倒序遍历结果一样的字符串,比如'aba', 'abcdedcba'。实现一个方法pal(),输入一个字符串,打印出以这个字符串为前缀的一个回文。比如输入'abc',pal()方法打印出'abcdcba'或'abcba';输入'abcb',可以输出'abcbcba'或'abcba'。如果可能,输出尽量短的结果。
【思路一】
以abcdc为例,以此为前缀的回文有 'abcdccdcba', 'abcdcdcba','abcdcba',即在输入的字符串后面添加字符,使之成为回文字符串
方法一、最先想到的办法就是把输入的字符串倒序拼接在原字符串后面,如原字符串为'abcdc',倒序为'cdcba',拼接的结果为'abcdccdcba',然后不断删除倒序的字符,拼接上去,判断是否是回文,是,则输出,不是,则继续删除字符。比如:
1)'abcdcdcba'是回文
2)'abcdccba'不是回文
3)'abcdcba'是回文
最后一个是回文的字符串即未最短的回文字符串。
这样的话,每次可能都求出几个没用的回文串,例如上面的'abcdcdcba'是回文,题目要求是求最短的回文串,因此我们从最短可能的回文串开始。
先判断字符串本身是不是回文串,如果不是,一次添加字符,a,ba,cba,dcba,cdcba判断。
#include <string.h>
#include <iostream>
using namespace std;
//判断是否是回文串
bool IsPalindrome(char* str){
int len = strlen(str);
for(int i = 0,j = len - 1;i < j;i++,j--){
if(str[i] != str[j]){
return false;
}
}
return true;
}
// 回文串修复
char* pal(char* s){
int len = strlen(s);
char* str = new char[2*len+1];
for(int i = 0;i < len;i++){
str[i] = s[i];
}
// 本身就是回文串
if(IsPalindrome(s)){
return s;
}
for(int i = 0;i < len;i++){
int index = len;
for(int j = i;j >= 0;j--){
str[index++] = s[j];
}
str[index] = '\0';
if(IsPalindrome(str)){
return str;
}
}
}
int main(){
char* str="amanaplanacanal";
cout<<pal(str);
return 0;
}
【思路二】
若需要找最短的回文,则要求在原字符串后面新添的字符串长度尽量短。只要在原字符串中找到某一位置,在此位置(含)后面全为回文,只要把此位置前的字符倒序追加在原字符串后即可。故只需要找出最前的该位置即可。
#include <string.h>
#include <iostream>
using namespace std;
//判断是否是回文串
bool IsPalindrome(char* str){
int len = strlen(str);
for(int i = 0,j = len - 1;i < j;i++,j--){
if(str[i] != str[j]){
return false;
}
}
return true;
}
// 回文串修复
char* pal(char* s){
int len = strlen(s);
char* str = new char[2*len+1];
for(int i = 0;i < len;i++){
str[i] = s[i];
}
// 修复
for(int i = 0;i < len;i++){
// 找到位置i,使i(含)后的字符串为回文
if(IsPalindrome(s+i)){
int index = len;
// 将i之前的字符倒序添加源字符串后
for(int j = i-1;j >= 0;j--){
str[index++] = s[j];
}
str[index] = '\0';
return str;
}
}
}
int main(){
char* str="xyz";
cout<<pal(str);
return 0;
}
分享到:
相关推荐
创新工场2013年校园招聘笔试试题.docx创新工场2013年校园招聘笔试试题.docx创新工场2013年校园招聘笔试试题.docx创新工场2013年校园招聘笔试试题.docx创新工场2013年校园招聘笔试试题.docx创新工场2013年校园招聘...
创新工场校园招聘试题2013,分享一下,希望能帮助大家
2012创新工场校园招聘笔试题,相当给力!
创新工场-2015-研发笔试题.PDF,答案在牛客网,0积分,免费下载!
创新工场 的笔试题目!希望对大家有帮助!是2011年的!明年也要找工作了!加油!
创新工场李开复:SoLoMo互联网未来发展模式 可以看看了解下
2015创新工场校招研发笔试题.pdf 2015届阿里巴巴校招测试开发工程师在线笔试题.pdf 2015年欢聚时代(YY)校园招聘Java笔试题目.pdf 2015年欢聚时代校园招聘C++笔试题目.pdf 2015网易校招JAVA开发工程师.pdf...
该文档来自MDCC 2014中国移动开发者大会。创新工场用户体验总监INWAY Design创始人吴卓浩发表的题为“O2O全流程用户体验设计”主题演讲,欢迎下载!
2012创新工场笔试题
创新工场.docx
创新工场的笔试题,20130916 1、socket客户端调用的函数是()
2015年创新工场校招研发笔试题,提前做,未雨绸缪
创新工场改变了啥.docx
创新工场CEO李开复“互联网的产品精神”.ppt
创新工场CEO李开复“互联网的产品精神”课件.ppt
信息通信产业园创新工场项目代管单位谈判投标书.doc
李开复:创新工场模式适合中国.docx
python毕业设计-基于Django+BootStrap编写的紫丁香创新工场网站设计与实现+使用说明.zippython毕业设计-基于Django+BootStrap编写的紫丁香创新工场网站设计与实现+使用说明.zip 【备注】 1、该资源内项目代码都经过...