题解 | 最长回文子串

#include <ios>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    int getLongestPalindrome(string A) {
        int n = A.size();
        vector<int> dp(n, 1);
        int result = 1;
        
        // 初始化前两位
        if(A[0] == A[1]){
            dp[1] = 2;
            result = 2;
        }
        
        for(int i = 1; i < n-1; i++){
            int j = i - dp[i] + 1;
            for(int k = max(j-1, 0); k <= i+1; k++){
                if(A[k] == A[i+1]){
                    int left = k;
                    int right = i+1;
                    // 验证回文
                    while(left < right && A[left] == A[right]){
                        left++;
                        right--;
                    }
                    // 验证通过，更新长度
                    if(left >= right){
                        dp[i+1] = i + 2 - k;
                        break; // 找到最优解，退出内层循环
                    }
                }
            }
            // 更新最大长度
            if(dp[i+1] > result)
                result = dp[i+1];
        }
        return result;
    }
};