最长回文子串

//https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/
//中心扩展法
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2)  return s;

        int left_max = 0, right_max = -1;
        for (int i = 0; i < n; ++i)
        {
            int left = i, right = i;
            while (left >= 0 && s[left] == s[i])    --left;
            while (right < n && s[right] == s[i])   ++right;
            while (left >= 0 && right < n && s[left] == s[right])
            {
                ++right;
                --left;
            }
            if (right - left > right_max - left_max)
            {
                right_max = right;
                left_max = left;
            }
        }

        return s.substr(left_max + 1, right_max - left_max - 1);
    }
};

//动态规划法
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2)    return s;
        // dp[i][j]标记从i到j是否是回文子串
        vector<vector<int>> dp(n, vector<int>(n));
        string ans;
        // length表示判断的子串的长度
        // left表示字串的左边起始位置
        // right表示字串的右边终止位置
        for(int length = 0; length < n; length++)
        {
            for(int left = 0; left + length < n; left++)
            {
                int right = left + length;
                if(length == 0) dp[left][right] = 1; 
                else if(length == 1)    dp[left][right] = (s[left] == s[right]); 
                else    dp[left][right] = (s[left] == s[right] && dp[left + 1][right - 1]);
                if(dp[left][right] && (length + 1) > ans.size())    ans = s.substr(left, length + 1);
            }
        }
        return ans;
    }
};