题解 | #最长回文子串#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    int getLongestPalindrome(string A) {
        // write code here
        const int len=A.size();
        vector<vector<bool>> dp(len,vector<bool>(len));

        int res=0;
        int count=0;
        for(int i=len-1;i>=0;i--){
            count=0;
            for(int j=i;j<len;j++){

               if(A[i]==A[j]){
                   if(j-i<=1){
                       count=j-i+1;//每次前行一步而已
                       dp[i][j]=true;
                   }
                   else if(dp[i+1][j-1])//里面的是否回文子串
                   {
                       count=j-i+1;
                       dp[i][j]=true;
                   }
               }

            }
            res=max(res,count);
        }
        return res;

    }
};

class Solution {
public:
    int fun(string& s, int begin, int end){
        //每个中心点开始扩展
        while(begin >= 0 && end < s.length() && s[begin] == s[end]){ 
            begin--;
            end++;
        }
        //返回长度
        return end - begin - 1; 
    } 
    int getLongestPalindrome(string A) {
        int maxlen = 1;
        //以每个点为中心
        for(int i = 0; i < A.length() - 1; i++) 
            //分奇数长度和偶数长度向两边扩展
            maxlen = max(maxlen, max(fun(A, i, i), fun(A, i, i + 1))); 
        return maxlen;
    }
};