[创新工场]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] = '';
        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] = '';
            return str;
        }
    }
}

int main(){
	char* str="xyz";
	cout<<pal(str);
	return 0;
}