题目描述
给你一个字符串 s
,找到 s
中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
样例
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"
算法
(枚举回文子串的中心点) $O(n^2)$
遍历字符串中每一个字符,找到以该字符为中心的最长回文子串
回文子串分为奇数子串和偶数子串
- 奇数子串:运用双指针,从中心字符的前一个字符和后一个字符开始向两头遍历,遍历到指针指向的字符不相同为止,指针之间的字符串为中心字符的最长奇数回文子串
- 偶数子串:同找奇数子串,一个指针指向中心字符,一个指针指向中心字符前一个字符
在遍历中不断更新找到的最长子串,最终得到的子串即为答案
时间复杂度
$$O(n^2)$$
C++ 代码
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 - 1, r = i;
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;
}
};