leetcode5 最长回文子串

题目来源：LeetCode5：最长回文子串

题目描述：

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

示例 1：

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

示例 2：

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

题解：

暴力解法不用。还有三种解法：

解法一：中心扩展算法

分奇数和偶数回文串长度两种情况。

class Solution {
public:
    int start=0,maxlen=0;
    string longestPalindrome(string s) {
        if(s.size()<1) return s;
        for(int i=0;i<s.size();i++)
        {
            int len1=getPalindrome(s,i,i);
            int len2=getPalindrome(s,i,i+1);
            int len=max(len1,len2);
            if(len>maxlen){
                maxlen=len;
                start=i-(maxlen-1)/2;
            }
        }
        return s.substr(start,maxlen);
    }
    int getPalindrome(string s,int left,int right)
    {
        if(s[left]!=s[right]) return 1;
        while(left>=0&&right<s.size()&&s[left]==s[right])
        {
            left--;
            right++;
        }
        return right-left-1;
    }
};

解法二：动态规划

二维数组dp[i][j]表示字符串s(i..j)是不是回文字符串，如果s[i]!=s[j]，那么显然不是回文，dp[i][j]=false，否则dp[i][j]=dp[i+1][j-1]。

故要求j-1-(i+1)+1<2，那么j-i<3,当j-i<3时，不需要dp，直接为true。对于dp数组矩阵，对角线的值为true，只用考虑上三角，因为i的值小于j的值。为了正确更新dp数组，动态规划的顺序是先从列从上到下，再从行从左到右，最终可以判断dp[0][s.size()-1]是否为回文，即字符串s是否为回文。在更新的期间更新回文的起始位置start和最大长度maxlen，最终根据这两个值截取字符串返回结果。

class Solution {
public:
    int start=0,maxlen=0;
    string longestPalindrome(string s) {
        int len=s.size();
        if(len<2) return s;
        vector<vector<bool>> dp(len,vector<bool>(len,false));
        int i,j;
        for(i=0;i<len;i++)
            dp[i][i]=true;
        int start=0,maxlen=1;
        for(j=0;j<len;j++){
            for(i=0;i<j;i++){
                if(s[i]!=s[j]) dp[i][j]=false;
                else{
                    if(j-i<3) dp[i][j]=true;
                    else dp[i][j]=dp[i+1][j-1];
                }
                if(dp[i][j]&&j-i+1>maxlen){
                    maxlen=j-i+1;
                    start=i;
                }
            }
        }
        return s.substr(start,maxlen);
    }
};

方法三：Manacher算法（略）