题解 | #最长回文子串#

中心扩散法：之前美团面试手撕的时候就用的这个方法，O(n)的方法还没做过不敢写就直接说不会，然后挂了😅

class Solution {
public:
    int fun(string &s, int begin, int end) {
        while(begin >= 0 && end < s.size() && s[begin] == s[end]) {
            begin--; end++;
        } return end-begin-1;
    }
 
    int getLongestPalindrome(string A) {
        int maxlen = -1;
        for(int i = 0; i < A.size(); i++) {
            maxlen = max(maxlen, max(fun(A, i, i), fun(A, i, i+1)));
        } return maxlen;
    }
};

dp做法：时间复杂度和空间复杂度都是O(n^2)。

class Solution {
public:
    int getLongestPalindrome(string &s) {
        int n = s.size();
        if (n < 2) return n;

        int maxLen = 1, begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        vector<vector<int>> dp(n, vector<int>(n));
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < n; i++)
            dp[i][i] = true;
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= n; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < n; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= n) break;

                if (s[i] != s[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return maxLen;
    }
};