题目描述
给你一个字符串 s,找到 s 中最长的 回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
样例
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母组成
(暴力枚举中心点(分奇偶)) $O(n^2)$
C++ 代码
class Solution {
public:
string longestPalindrome(string s) {
string res;
for (int i = 0; i < s.size(); i ++)
{
for (int j = i, k = i; j >=0 && k < s.size() && s[j] == s[k]; j --, k ++)
if (res.size() < k - j + 1)
res = s.substr(j, k - j + 1);
for (int j = i, k = i + 1; j >=0 && k < s.size() && s[j] == s[k]; j --, k ++)
if (res.size() < k - j + 1)
res = s.substr(j, k - j + 1);
}
return res;
}
};