Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

// 非dp方法
class Solution {
public:
    int index = 0, maxLength = 0;
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) return s;
        for (int i = 0; i < n; ++i)
        {
            update(s,i,i);
            update(s,i,i+1);
        }
        return s.substr(index,maxLength);
    }
    
    void update(string s, int i, int j)
    {
        while(i >= 0 && j < s.size() && s[i] == s[j])
        {
            --i;
            ++j;
        }
        int length = j - i - 1;
        if (maxLength < length)
        {
            index = i + 1;
            maxLength = length;
        }
    }
}

 

// dp 方法
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) return s;
        vector<bool> temp(n);
        vector<vector<bool>> dp;
        dp.resize(n,temp);
        int index = 0, maxLength = 0;
        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = i; j < n; ++j)
            {
                dp[i][j] = ((s[i] == s[j]) && (j - i < 3 || dp[i + 1][j - 1]));
                if (dp[i][j] && maxLength < j - i + 1)
                {
                    index = i;
                    maxLength = j - i + 1;
                }
            }
        }
        return s.substr(index, maxLength);
    }
};