题解 | #最长回文子串#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    int getLongestPalindrome(string A) {
        // write code here
        if(A.size() < 2) return A.size();
        //首先定义一个二维数组，用来进行动态规划
        vector<vector<bool>> dp(A.size(), vector<bool>(A.size()));
        int maxlen = 1;
        int begin = 0;
         //将对角线上的元素初始化为true
        for(int i = 0; i < A.size(); i++){
            dp[i][i] = true;
        }
        //一列一列的遍历dp，当i j 指向的元素相等时，就进行判断，当i - j + 1 < 3,也就是该字符串长度小于2时，就直接等于true，否则dp的值依赖于dp[i+1][j-1]的值
        for(int j = 1; j < A.size(); j++){
            for(int i = 0; i < j; i++){
                if(A[i] != A[j]) dp[i][j] = false;
                else{
                    if(j - i < 3 ) dp[i][j] = true;//表示字符串只有长度为3,2
                    else dp[i][j] = dp[i+1][j-1];
                }

                //最后若dp为true且长度变大，则对maxlen和begin进行gengxin
                if(dp[i][j] == true && j - i + 1>maxlen){
                    maxlen = j - i + 1;
                    begin = i;
                }
            }
        }
        return  maxlen;
         

    }
};