5. 最长回文子串

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

示例 1：

1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

1
2
输入: "cbbd"
输出: "bb"

Solution1：

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
class Solution {
public:
    int expandAroundCenter(string s, int left, int right){
        int L = left, R = right;
        while(L >= 0 && R < s.size() && s[L] == s[R]){
            L--;
            R++;
        }
        return R - L - 1;
    }
    string longestPalindrome(string s) {
        if( s.size() < 1) return "";
        int start = 0, end = 0;
        for(int i = 0; i < s.size(); i++){
            //以i为中心点开始探测。
            int len1 = expandAroundCenter(s,i,i);
            //以i与i+1位置的之间开始探测。
            int len2 = expandAroundCenter(s,i,i+1);
            int len = max(len1,len2);
            if(len > end-start){
                start = i - (len-1)/2;
                end = i + len/2;
            }
        }
        return s.substr(start,end-start+1);
    }
};
思路：

只想到了O(n3)复杂度的暴力解法。看题解做的。

由于回文串的两侧互为镜像，所以可以从中心向两侧展开进行探测。一共会有2n-1个中心点（一个点为中心，两点之间也可以看作一个中点）。
时间复杂度为O(n2);