题解 | #最长回文子串#

#include <algorithm>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    int getLongestPalindrome(string A) {
        if(A.size()==0 || A.size()==1){return A.size();}
        if (A.size()==2 && A[0]==A[1]) {return 2;}
        else if (A.size()==2 && A[0]!=A[1]) {return 1;}
   
        //dp[i][j]表示子串左边i所指字符与子串右边j所指字符是否相等，相等为一，否则为0
        vector<vector<int>>dp(A.size(),vector<int>(A.size(),0));
        //dp[i][i]表示子串左边i所指字符与子串右边i所指字符相等,为1
        for(int i =0;i<A.size();i++){
            dp[i][i]=1;
        }
        //dp[i][i+1]表示子串左边i所指字符与子串右边i+1所指字符s是否相等,相等为1，否则为0
        for(int i =0;i<A.size()-1;i++){//谨防数组越界
            if (A[i]==A[i+1]) {
                dp[i][i+1]=1;
            }
            else {dp[i][i+1]=0;}
        }
        int maxlength =1;
        for (int len = 3; len <= A.length(); len++) {
            for (int i = 0; i+ len-1< A.length(); i++) {
                int j = i + len - 1;
                if (A[i] == A[j] && dp[i + 1][j - 1] == 1) {
                    dp[i][j] = 1;
                    maxlength = max(maxlength, len);
                }
                else{dp[i][j] = 0;}
            }
    }
    return maxlength;
    }
};