最长回文子串

1. 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

• 输入: "babad"
• 输出: "bab"

注意: "aba" 也是一个有效答案。

示例 2：

• 输入: "cbbd"
• 输出: "bb"

方法一：暴力法

很明显，暴力法将选出所有子字符串可能的开始和结束位置，并检验它是不是回文。

复杂度分析：
时间复杂度：因为验证每个子字符串需要 O(n) 的时间，所以运行时间复杂度是 O(n^3)。
空间复杂度：O(1)。

方法三：动态规划

为了改进暴力法，我们首先观察如何避免在验证回文时进行不必要的重复计算。考虑 “ababa” 这个示例。如果我们已经知道 “bab” 是回文，那么很明显，“ababa” 一定是回文，因为它的左首字母和右尾字母是相同的。

我们给出 P(i,j)的定义如下：

这产生了一个直观的动态规划解法，我们首先初始化一字母和二字母的回文，然后找到所有三字母回文，并依此类推…

复杂度分析：
时间复杂度：O(n^2)，这里给出我们的运行时间复杂度为 O(n^2)。
空间复杂度：O(n^2)，该方法使用 O(n^2)的空间来存储表。

方法三：中心扩展算法

事实上，只需使用恒定的空间，我们就可以在 O(n^2)的时间内解决这个问题。

我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n - 1个这样的中心。

你可能会问，为什么会是 2n - 1 个，而不是 n 个中心？原因在于所含字母数为偶数的回文的中心可以处于两字母之间（例如 “abba” 的中心在两个‘b’ 之间）。

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.length()<=1)
            return s;
        int len=s.length();
        int max=1,begin=0;
        for(int i=0;i<len;++i){
            int len1=longestPalindromeCore(s, i, i);
            int len2=longestPalindromeCore(s, i, i+1);
            int n=(len1>len2? len1:len2);
            if(max<n){
                max=n;
                begin=i-(max-1)/2;
            }
        }
        return string(s.begin()+begin,s.begin()+begin+max);
    }
    int longestPalindromeCore(string s, int left, int right) {
        while(left>=0 && right <s.length() && s[left]==s[right]){
            --left;
            ++right;
        }
        return right-left-1;
    }
};