5.最长回文子串

1、动态规划算法

class Solution {
public:
    string longestPalindrome(string s) {
        int len=s.size();
        if(len==0||len==1) return s;
        int start=0;
        int max=1;
        vector<vector<int>> dp(len,vector<int>(len));
        for(int i=0;i<len;i++)   //初始化主对角线和次对角线
        {
            dp[i][i]=1;
            if(i<len-1&&s[i]==s[i+1])
            {
                dp[i][i+1]=1;
                max=2;
                start=i;
            }
        }
        for(int l=3;l<=len;l++)   
        {
            for(int i=0;i+l-1<len;i++)
            {
                int j=l+i-1;
                if(s[i]==s[j]&&dp[i+1][j-1]==1)
                {
                    dp[i][j]=1;
                    start=i;
                    max=l;
                }
            }
        }
        return s.substr(start,max);
    }
};

2、中心扩展算法

长度为n的字符串共有2n-1个中心扩展点，比如“abc”中心扩展点为b，“abba”中心扩展点为“bb”。

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size()==0)
            return "";
        int start=0;
        int max=1;
        for(int i=0;i<s.size();i++)
        {
            int len1=expandAroundCenter(s,i,i);  //奇数扩展
            int len2=expandAroundCenter(s,i,i+1);   //偶数扩展
            int len=len1>len2?len1:len2;
            if(len>=max)
            {
                start=i-(len-1)/2;
                max=len;
            }
        }
        return s.substr(start,max);
        
    }
    int expandAroundCenter(string s,int left,int right)
    {
        while(left>=0&&right<s.size()&&s[left]==s[right])    //注意边界条件防止越界
        {
            --left;
            ++right;
        }
        return right-left-1;   //注意返回值
    }
};