题解 | #最长回文子串#直观解法+动态规划

//1 #直观解法
//时间复杂度 o(n*n)
//空间复杂度 o(1)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    int getLongestPalindrome(string A) {
        int maxi = 1, n = A.length();
        for(int i=0;i<n;++i) {
            int cur = 1;
            for(int j=1;i-j>=0&&i+j<n;++j)
                if(A[i-j] == A[i+j]) cur += 2;
                else break;
            maxi = max(maxi,cur);

            if(i<n-1 && A[i]==A[i+1]) {
                int cur = 2;
                for(int j=1;i-j>=0&&i+j+1<n;++j)
                    if(A[i-j]==A[i+j+1]) cur += 2;
                    else break;
                maxi = max(maxi,cur);
            }
        }
        return maxi;
    }
};


//2 #动态规划
//时间复杂度 o(n*n)
//空间复杂度 o(n*n)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    int getLongestPalindrome(string A) {
        int maxi = 1, n = A.length();
        vector<vector<bool>> dp(n,vector<bool>(n));
        for(int i=0;i<n;++i) {
            for(int j=0;j<n;++j) {
                int a = min(i,j), b = max(i,j);
                if(a==b) dp[a][b] = true;
                else if(b-a==1) dp[a][b] = A[b]==A[a];
                else dp[a][b] = A[b]==A[a]&&dp[a+1][b-1];
                if(dp[a][b]) maxi = max(maxi,b-a+1);
            }
        }
        return maxi;
    }
};