题目描述
给你一个字符串 s,找到 s 中最长的回文子串。
样例
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
算法1
(暴力枚举) $O(n^2)$
首先,最长回文串包含两种,一种是长度恰好为奇数的,另一种是恰好长度为偶数的。
因此这里需要枚举两种情况。因此我们在这里不妨枚举字符串的中心位置是哪一个位置。
以此达到不重不漏的目的。
-
当回文串为奇数时,
定义l = i - 1, r = i + 1
,然后找出最左端与最右端,需要注意的是最后一次循环的时候
s[l]
与s[r]
不相等(除去他们越界的情况,即使越界的话也不会影响后面的结果表达)
if(res.size() < r - l - 1)
此时更新答案
区间为[l+1,r-1]
此时区间的长度为r - 1 - (l - 1) + 1 = r - l - 1
此时字符串为s.substr(l + 1, r - l - 1)
-
当回文串为偶数时,左右两个起始的枚举端点为
i , i + 1
之后的处理过程类似于奇数回文串
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,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;
}
};