LeetCode学习（5）Shortest Palindrome（最短回文串）_lua输入一个字符串,创建它的最短回文串

1.问题描述
Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given “aacecaaa”, return “aaacecaaa”.
Given “abcd”, return “dcbabcd”.
给定一个字符串，在字符串的前面加入字符，将该字符串变成一个最短的回文字符串，如题目中所示aacecaaa变成最短的回文只需要在前面加上字符a ，得到回文字符串aaacecaaa
2.代码时刻

//c++ VS2013
#include<iostream>
#include<string>
using namespace std;
bool Check(string s, int low, int high)
{
    //该函数主要判断从low到high的字符串是否为回文字符串
    if (low == high)
        return true;
    while (low<high)
    {
        if (s[low] != s[high])
            return false;
        low++;
        high--;
    }
    return true;
}
string ShortestPalindrome(string s)
{
    int i, j;
    int len;
    string result = "";
    len = s.length() - 1;
    if (len <= 0)
        return "";
    for (len; len>0; len--)  //从输入的字符串最后一位开始往前找，找到满足回文的最大回文字符串 
    {
        if (s[0] == s[len] && Check(s, 0, len))
            break;
    }
    /*找到第1-len位表示最长的回文串，第(len+1)-length()位就是没有匹配上的，反转第(len+1)-length()位并加在原来字符串最前面就是*/
    for (i = s.length() - 1; i>len; i--)
        result += s[i];
    result += s;
    return result;
}
int main()
{   
    string s = "xixl";
    string a = ShortestPalindrome(s);
    cout<<a << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

3.测试结果
测试用例： s = “xixl”
测试结果： s=”lxixil”

测试用例： s = “aaacaaafigh”
测试结果： s = “hgifaaacaaafigh”