题目描述

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

示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：

输入: “cbbd”
输出: “bb”

算法1 （暴力枚举）$O(n^2)$

枚举字符串的每个子串，然后判断这个子串是否是回文的，

时间复杂度

枚举每个子串的时间复杂度是$O(n^2)$，然后判断这个子串是否回文时间复杂度$O(n)$；所以算法的总体时间复杂度是$O(n^3)$；毫无疑问TLE。

代码

class Solution {
public:
    bool is_parlindrome(string &s, int l, int r){//判断是否回文
        while(l < r)
            if(s[l] == s[r]) l ++ , r -- ;
            else return false;
        return true;
    }
    string longestPalindrome(string s) {
        int n = s.size();
        int l = 0, r = 0;
        for(int i = 0; i < n; i ++ )//枚举所有子串
            for(int j = 0; j <= i; j ++ )
                if(is_parlindrome(s, j, i)&& r - l < i - j)
                    l = j, r = i;
        return s.substr(l, r - l + 1);
    }
};

算法2（暴力枚举）O(n^2)

回文字符串可以分两种情况讨论，
第一种情况如果回文字符串的长度是奇数的话，那么表示这个回文字符串的中心是有一个单独的字母，这个字母的左右部分是对称的，比如“aba”, “abcba”;
第二种情况就是回文字符串的长度是偶数，表示可以将这个字符串对半分为两部分，这两部分是对称的，比如”aa”、“abba”、“abccba”。
所以我们要做的就是枚举字符串中每个可能的回文字符串的中心，然后以这个中心向外扩展。举例来说，对于“abccba”来说，我们可以枚举“a为中心”，“ab为中心”，“b为中心”，“bc为中心”、“c为中心”、“cc为中心”等等情况。其实我们可以看到当以两个字符为中心的时候，有些情况是不满足的，可以直接pass掉。

时间复杂度

用这种方法，我们可以枚举到2n - 1 个回文中心，向外扩展的时间复杂度是O(n),那么算法的总体时间复杂度就是$O(n^2)$.
虽然和算法1一样 是暴力枚举，但是时间复杂度却可以少一个量级。这种方法可以通过。

代码

class Solution {
public:
    int palindrome(string &s, int l, int r, int n){//找到以l、r为中心的最长回文子串，注意传引用
        while(~l && r < n && s[l] == s[r]) l --, r ++ ;//如果相等就向外扩展.~i表示i!=-1
        return r - l - 1;//此时l，r指向的是回文字符串边界的外侧字符，比如“xabcbay”，
                         //以c为中心，运行完毕后l指向x，y指向r，所以实际长度要-2
    }
    string longestPalindrome(string s) {
        int n = s.size();
        int start = 0, len = 0;
        int i = 0, j = 0;
        while(i < n && j < n){
            if(s[i] == s[j]){
                int l = palindrome(s, i, j, n);
                if(l > len){
                    start = i - (l - 1) / 2;//计算起始点
                    len = l;
                }
            }
            if(i == j) j ++ ;//枚举中心
            else i ++ ;
        }
        return s.substr(start, len);
    }
};

算法3 （动态规划）

如果s[i : j]为回文串，那么一定满足s[i + 1 : j - 1]是回文串，并且s[i] == s[j];
状态转移方程： dp[l][r] = dp[l + 1][r - 1] && (s[l] == s[r]);

时间复杂度

我们从枚举所有子串，时间复杂度为$O(n^2)$,判断这个子串是否为回文串，时间复杂度为O(1),所以算法的总体时间复杂度为$O(n^2)$

代码

class Solution {
    static const int N = 1010;
    bool dp[N][N];
public:
    string longestPalindrome(string s) {
        int n = s.size();
        memset(dp, false, sizeof dp);
        int len = 2;
        int start = 0, length = 0;
        for(int len = 1; len <= n; len ++ ){//枚举长度
            for(int i = 0; i + len - 1 < n; i++){//枚举起点
                int l = i, r = i + len - 1;
                if(len == 1) dp[i][i] = true;//只有一个字母，是回文串
                else if(len == 2) dp[l][r] = s[l] == s[r];//两个字母
                else{
                    dp[l][r] = dp[l + 1][r - 1] && (s[l] == s[r]);
                }
                if(dp[l][r] && r - l + 1 >= length){//记录最大长度和起点
                    length = r - l + 1;
                    start = l;
                }
            }
        }

        return s.substr(start, length);
    }
};

算法4（manacher算法）

manacher算法可以算出回文子串的最大长度。算法的具体过程请百度一下。大概就是加工字符串，然后遍历一遍字符，计算每个字符串的回文半径.
这道题的思路就是用manacher的模板，记录最大回文半径出现的位置，然后把最长的回文子串拼出来输出。

manacher模板

char S[N];
int cnt[N];

int manacher(string s){
    int n = s.size();
    int l = 0, R = 0, C = 0;
    S[l ++ ] = '$';
    S[l ++ ] = '#';
    for(int i = 0; i < n; i ++ ){
        S[l ++ ] = s[i];
        S[l ++ ] = '#';
    }
    S[l] = 0;
    int res = 0;
    for(int i = 0; i < l; i ++ ){
        cnt[i] = R > i ? min(cnt[2 * C - i], R - i) : 1;
        while(i + cnt[i] > 0 && i - cnt[i] < l)
            if(S[i + cnt[i]] == S[i - cnt[i]]) cnt[i] ++ ;
            else break;
        if(i + cnt[i] > R){
            R = i + cnt[i];
            C = i;
        }
        res = max(res, cnt[i]);
    }
    return res - 1;
}

代码

class Solution {
public:
    static const int N = 1010, M = 2 * N;
    char S[M];
    int cnt[M];
    string manacher(string s){
        int l = 0, R = 0, C = 0;
        int cur = 0;
        int n = s.size();
        S[l ++ ] = '$';
        S[l ++ ] = '#';
        for(int i = 0; i < n; i ++ ){
            S[l ++ ] = s[i];
            S[l ++ ] = '#';
        }
        S[l] = 0;

        for(int i = 0; i < l; i ++ ){
            cnt[i] = R > i ? min(cnt[2 * C - i], R - i) : 1;
            while(i - cnt[i] > 0 && i + cnt[i] < l)
                if(S[i - cnt[i]] == S[i + cnt[i]]) cnt[i] ++ ;
                else break;
            if(i + cnt[i] > R){
                R = i + cnt[i];
                C = i;
            }
            if(cnt[i] > cnt[cur]) cur = i;
        }
        int left = cur - cnt[cur] + 1, right = cur + cnt[cur] - 1;
        string best = "";
        for(int i = left; i <= right; i ++ )
            if(S[i] != '#' && S[i] != '$') best += S[i];
        return best;
    }
    string longestPalindrome(string s) {
        return manacher(s);
    }
};