[5]最长回文子串

//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 示例 3： 
//
// 
//输入：s = "a"
//输出："a"
// 
//
// 示例 4： 
//
// 
//输入：s = "ac"
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母（大写和/或小写）组成 
// 
// Related Topics 字符串 动态规划 
// 👍 3225 👎 0

/*
* 5 最长回文子串
* 2021-02-22 17:18:48
* @author oxygenbytes
*/ 
#include "leetcode.h" 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    string str;
    string longestPalindrome(string s) {
        str = s;
        const int n = s.size();
        int len = 0, left, right;

        for(int i = 0;i < n;i++) {
            int x = i, y = i;
            int a = aux(x, y);
            if (a > len) {
                len = a;
                left = x;
                right = y;
            }
            x = i, y = i + 1;
            int b = aux(x, y);
            if (b > len) {
                len = b;
                left = x;
                right = y;
            }
        }
        return s.substr(left, right - left + 1);
    }

    int aux(int& left, int& right){
        const int n = str.size();
        while(left >= 0 && right < n && str[left] == str[right])
            left--, right++;
        left++;
        right--;
        return right - left + 1;
    }
};

class Solution2 {
public:
    string longestPalindrome(string s) {
        if(s.size() < 2) return s;
        const int n = s.length();
        int maxLeft = 0;
        int maxLength = 1;
        vector<vector<bool>> dp(n,vector<bool>(n,false));

        for(int i = 0;i < n;i++){
            for(int j = 0;j < i;j++){
                if(s[i] == s[j] && ((i - j) <= 2 || dp[j+1][i-1])){
                    dp[j][i] = true;
                    if(i - j + 1 > maxLength){
                        maxLeft = j;
                        maxLength = i - j + 1;
                    }
                }
            }
        }
        return s.substr(maxLeft, maxLength);
    }
};
//leetcode submit region end(Prohibit modification and deletion)