题解 | #最长回文子串#

中心扩散法：

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        if(n < 2) return n;
        int left, right, maxlen = 1;
        for(int i = 0; i < n; i++) { //以每个字符为中心左右扩散
            //长度为奇数时
            left = i;
            right = i;
            while(left >= 0 && right < n) { //确保不越界
                if(A[left] == A[right]) { //判断左右字符是否相等
                    maxlen = max(maxlen, right - left + 1); //相等时更新最大长度
                    left--;
                    right++; //左右各扩散一位
                }
                else break; //若不相等则退出循环
            }
            //长度为偶数时
            left = i;
            right = i + 1; 
            while(left >= 0 && right < n) { //原理同上
                if(A[left] == A[right]) {
                    maxlen = max(maxlen, right - left + 1);
                    left--;
                    right++;
                }
                else break;
            }
        }
        return maxlen; //返回最大值
    }
};

动态规划：

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        if(n < 2) return n;
        int maxlen = 1;
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = 0; i < n; ++i) {
            dp[i][i] = 1; //长度1一定为回文
        }
        for(int i = 2; i <= n; i++) { //从短到长对每种长度分别判断，可以这么做是因为判断较长的需要利用较短的
            for(int j = 0; j < n - i + 1; j++) { //从头开始对长度i+1的子字符串判断
                if(i == 2) {
                    dp[j][j + 1] = (A[j] == A[j + 1]); //长度2判断头尾是否相等
                }
                else {
                    if(A[j] == A[j + i - 1]) 
                        dp[j][j + i - 1] = dp[j + 1][j + i - 2]; //长度大于等于3，判断两头是否相等，若相等则同去两头的bool值一样
                    else 
                        dp[j][j + i - 1] = 0; //否则为0
                }
                if(dp[j][j + i - 1]) maxlen = max(maxlen, i); //更新最大值
            }
        }
        return maxlen;
    }
};