5.jpeg

    代码 :

    1. // 中心拓展
    2. class Solution {
    3. public:
    4.     string longestPalindrome(string s) {
    5.         int res = INT_MIN; 
    6.         string ans = "";
    7.         for(int i = 0; i < s.size(); i ++){
    8.             // odd 
    9.             for(int l = i, r = i; l >=0 && r < s.size(); l--, r++) {
    10.                 if(s[l] == s[r]) {
    11.                     res = max(res, r - l + 1);
    12.                     if(res == r - l + 1)
    13.                         ans = s.substr(l, r - l + 1);
    14.                 }
    15.                 else break; 
    16.             }
    18.             // even 
    19.             for(int l = i, r = i + 1; l >= 0 && r < s.size(); l--, r++) {
    20.                 if(s[l] == s[r]) {
    21.                     res = max(res, r - l + 1);
    22.                     if(res == r - l + 1)
    23.                         ans = s.substr(l, r - l + 1);
    24.                 }
    25.                 else break; 
    26.             }
    27.         }
    29.         return ans; 
    30.     }
    31. };
    // 动态规划
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size(); 
        vector<vector<bool>> dp(n, vector<bool>(n, false));

        int res = INT_MIN;  
        string ans = "";

        for(int r = 0; r < s.size(); r ++) {
            for(int l = 0; l <= r; l ++) {
                if(l == r) dp[l][r] = true; 
                else if (s[l] == s[r]) {
                    if(r - l + 1 == 2) dp[l][r] = true; 
                    else if (dp[l+1][r-1]) dp[l][r] = true; 
                }

                if(dp[l][r]){
                    res = max (res, r - l + 1); 
                    if(res == r - l + 1) {
                        ans = s.substr(l, r - l + 1);
                    }
                }
            }
        }

        return ans; 
    }
};