题目内容

给你一个字符串 s，找到 s 中最长的回文子串。

示例

示例 1：
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：”bb”

示例 3：
输入：s = “a”
输出：”a”

示例 4：
输入：s = “ac”
输出：”a”

提示

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

题解

根据回文串的特征来求解本题。
首先，当回文串的字符数量为奇数时，一定以某个点为中心，然后字符对称相等；当回文串的字符数量为偶数时，一定以中间两个点为中心，然后字符对称相等。根据这一点，我们可以遍历整个数组，枚举每一个点为中心的情况，最终求出全局回文串最大长度。
tips:
以i为中心，遍历奇数的情况和偶数的情况。奇数，则初始化l = i - 1,r = i + 1。偶数，则初始化l = i, r = i + 1

代码

class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        for(int i = 0; i < s.size(); i++){
            //长度为奇数的情况
            int l = i - 1,r = i + 1;
            while(l >= 0 && r < s.size() && s[l] == s[r]){
                l --;
                r ++;
            }

            if(res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);

            //长度为偶数的情况
            l = i, r = i + 1;
            while(l >= 0 && r < s.size() && s[l] == s[r]){
                l --;
                r ++;
            }

            if(res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);
        }
        return res;
    }
};