本文主要是介绍[创新工场]2014创新工场校园招聘之回文串修复，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目】
所谓回文，就是正序和倒序遍历结果一样的字符串，比如'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;
}
这篇关于[创新工场]2014创新工场校园招聘之回文串修复的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
