题目描述

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

样例

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

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

算法1

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

C++ 代码

class Solution {
public:
    bool judge(const string& s, int l, int r){
        while(l<=r){
            if(s[l]!=s[r])return false;
            l++;
            r--;
        }
        return true;
    }
    string longestPalindrome(string s) {
        if(s.empty())return s;
        string ls;
        for(int i=0;i<s.size();i++)
            for(int j=i;j<s.size();j++)
                if(j-i+1>ls.size()&&judge(s,i,j))ls=s.substr(i, j-i+1);
        return ls;
    }
};

算法2

(动态规划) $O(N^2)$

状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。
dp[i][j]=(s[i]==s[j]&&(j-i<=2||dp[i+1][j-1]))

时间复杂度

$O(N^2)$

C++ 代码

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.empty())return s;
        int sz=s.size();
        string ls;
        vector<vector<int>> dp(sz, vector<int>(sz));
        for(int i=0;i<sz;i++){
            for(int j=0;j<=i;j++){
                dp[j][i]=(s[i]==s[j]&&(i-j<2||dp[j+1][i-1]));
                if(dp[j][i]&&i-j+1>ls.size())ls=s.substr(j, i-j+1);
            }
        }
        return ls;
    }
};

算法3

(中心扩展) $O(N^2)$

奇数偶数中心扩展

时间复杂度

$O(N^2)$

C++ 代码

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.empty())return s;
        int sz=s.size();
        string ls;
        for(int i=0;i<sz;i++){
            int l=i, r=i, l1=0, l2=0;
            //奇数扩展
            while(l>=0&&r<sz&&s[l]==s[r])l1++, l--, r++;
            //偶数扩展
            l=i, r=i+1;
            while(l>=0&&r<sz&&s[l]==s[r])l2++, l--, r++;
            if(2*l1-1>l2*2){
                if(2*l1-1>ls.size())ls=s.substr(i-l1+1, 2*l1-1);
            }else{
                if(2*l2>ls.size())ls=s.substr(i-l2+1, 2*l2);
            }
        }
        return ls;
    }
};