题解 | #最长回文子串#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */
    int getLongestPalindrome(string A) {
        int len = A.length();
        vector<vector<int> > dp(len, vector<int>(len,
                                0));// dp[i][j]:i~j字符串是否回文
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }
        for (int m = 1; m < len; m++) { // 子串：01,12,23;02,13;03(根据这个画一遍就会了)
            for(int i=0; i<len-m; i++) {
                int j=i+m;//沿主对角线方向
                if(abs(i-j) == 1 && A[i] == A[j]) {
                    dp[i][j] = 1;
                    continue;
                }
                if(A[i] == A[j] && dp[i+1][j-1] == 1) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        int max = 0;
        for(int i=0; i<len; i++) {
            for(int j=0; j<len; j++) {
                if(dp[i][j] == 1 && (j-i)>max) {
                    max = j-i;
                }
            }
        }
        return max+1;
    }
};

恶心心的题目，看了解析还是花了好久才搞出来。