题目描述

给定一个字符串，返回它的最长回文子串。如果存在多个答案，返回任意一个即可。字符串长度 $\leq$ 1000。

样例1

输入："babad"
输出："bab"
注意："aba" 也是一个合法的答案.

样例2

输入："cbbd"
输出："bb"

算法

（暴力枚举） $O(n^2)$

由于字符串长度小于1000，因此我们可以用 $O(n^2)$ 的算法枚举所有可能的情况。
首先枚举回文串的中心 $i$，然后分两种情况向两边扩展边界，直到遇到不同字符为止:

• 回文串长度是奇数，则依次判断 $s[i-k] == s[i+k], k = 1, 2, 3, … $
• 回文串长度是偶数，则依次判断 $s[i-k] == s[i+k-1], k = 1, 2, 3, …$

如果遇到不同字符，则我们就找到了以 $i$ 为中心的回文串边界。

时间复杂度分析：一共两重循环，所以时间复杂度是 $O(n^2)$。

C++ 代码

class Solution {
public:
    string longestPalindrome(string s) {
        int res = 0;
        string str;
        for (int i = 0; i < s.size(); i ++ )
        {
            for (int j = 0; i - j >= 0 && i + j < s.size(); j ++ )
                if (s[i - j] == s[i + j])
                {
                    if (j * 2 + 1 > res)
                    {
                        res = j * 2 + 1;
                        str = s.substr(i - j, j * 2 + 1);
                    }
                }
                else break;

            for (int j = i, k = i + 1; j >= 0 && k < s.size(); j -- , k ++ )
                if (s[j] == s[k])
                {
                    if (k - j + 1 > res) 
                    {
                        res = k - j + 1;
                        str = s.substr(j, k - j + 1);
                    }
                }
                else break;
        }
        return str;
    }
};