题解 | #最长回文子串#

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

思路：中心扩散算法。

回文串是中心对称的，所以枚举字符串中每一个字符为中心，向两边扩散看能否形成回文串。

另外还可以用动态规划。

应该没有面试官会让你手撕马拉车吧？