题目描述

给定一个字符串，返回它的最长回文子串。如果存在多个答案，返回任意一个即可。字符串长度 ≤≤ 1000。

样例

输入："babad"
输出："bab"
注意："aba" 也是一个合法的答案.

算法0

(intuitive way) $O(n^2)$

最容易想到的方法是reverse然后找前后两条string的LCS. 但这是不对的。如果原序列中分别包含两条不邻接的互为reverse的substring，就会被算入LCS，但其实这并不是palindromic的。所以还需要检查一下LCS的index是否一致。

时间复杂度分析：与寻找最长公共子序列的复杂度一致。$O(n^2)$

C++ 代码

blablabla

算法1

(暴力枚举) $O(n^3)$

枚举所有substring 判断是否palindrome。

时间复杂度分析：substring(including a char itself)一共有C(n,2)+n。判断是否palindrome要O(n)，一共$O(n^3)$

C++ 代码

blablabla

算法2

(dp) $O(n^2)$

p(i, j) reperesent whether the substring between i and j (inclusive) is a palindrome.

transition function: p(i, j) = p(i+1, j-1) && (s[i] == s[j])
base case: p(i, i) = true; p(i, i+1) = (s[i] == s[i+1]);

时间复杂度分析：时间$O(n^2)$ 空间$O(n^2)$(two dimentional array p)

C++ 代码

class Solution {
public:
    string maxStr = "";
    string longestPalindrome(string s) {
        if(!s.length())
            return maxStr;
        if(s.length()==1) 
            return s;
        int n = s.length();
        bool p[n][n] = {false};
        for(int i = 0; i < n-1; i++){
            p[i][i] = true;
            p[i][i+1] = (s[i] == s[i+1]);
        }
        p[n-1][n-1] = true;
        p[n-2][n-1] = (s[n-2] == s[n-1]);
        for(int j = 2; j < n; j++){
            for(int i = j-2; i >= 0; i--){
                p[i][j] = (p[i+1][j-1] && s[i] == s[j]);
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = i; j < n; j++){
                if(p[i][j] && (j-i+1 > maxStr.length())){
                    printf("pij = %d %d %d \n", i, j, p[i][j]);
                    maxStr = s.substr(i, j-i+1);
                }
            }
        }
        return maxStr;
    }
};

算法3

(yxc的方法 枚举center and expand from the center) $O(n^2)$

时间复杂度分析：时间$O(n^2)$ 一共有2n-1个center。每个center expand O(n)。

C++ 代码

class Solution {
public:
    string maxStr = "";
    string longestPalindrome(string s) {
        if(!s.length() || s.length()==1) return s;
        for(int i = 0; i < s.size(); i++){
            for(int j = 0; i-j>=0 && i+j<s.length(); j++){
                if(s[i-j] == s[i+j]){
                    //printf("i-j= %d, i+j= %d\n", i-j, i+j);
                    //printf("i = %d, j = %d\n", i, j);
                    if(j*2+1 > maxStr.length())
                        maxStr = s.substr(i-j, j*2+1);
                }
                else break;

            }
            for(int j = 0; i-j>=0 && i+1+j<s.length(); j++){
                if(s[i] == s[i+1] && s[i-j] == s[i+1+j]){
                    if (j*2+2 > maxStr.length())
                        maxStr = s.substr(i-j, j*2+2);
                }
                else break;

            }
        }
        return maxStr;
    }
};

算法4

Manacher’s Algorithm $O(n)$

并没有看太懂……要是yxc大佬有空求写一下通俗讲解版本。

时间复杂度分析： $O(n)$

C++ 代码

class Solution {
public:
    string longestPalindrome(string s) 
    {
        string T;// Transform S to T
        for(int i=0;i<s.size();i++)
            T+="#"+s.substr(i,1);
        T.push_back('#');

        vector<int> P(T.size(),0); // Array to record longest palindrome
        int center=0,boundary=0,maxLen=0,resCenter=0;
        for(int i=1;i<T.size()-1;i++) {
            int iMirror=2*center-i; // calc mirror i = center-(i-center)
            P[i]=(boundary>i)?min(boundary-i,P[iMirror]):0; // shortcut
            while(i-1-P[i]>=0&&i+1+P[i]<=T.size()-1&&T[i+1+P[i]] == T[i-1-P[i]]) // Attempt to expand palindrome centered at i
                P[i]++;
            if(i+P[i]>boundary) { // update center and boundary
                center = i;
                boundary = i+P[i];
            }
            if(P[i]>maxLen) { // update result
                maxLen = P[i];
                resCenter = i;
            }    
        }
        return s.substr((resCenter - maxLen)/2, maxLen);
    }
};