5. 最长回文子串
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"
示例 3:
输入:s = "a"
输出:"a"
示例 4:
输入:s = "ac"
输出:"a"
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母(大写和/或小写)组成
解题思路:
中心扩散法
我们是以每一个字符为中心,往两边扩散,来求最长的回文子串。
我们来思考这样一个问题,如果是单个字符,我们可以认为他是回文子串,如果是多个字符,并且他们都是相同的,那么他们也是回文串。所以对于上面的问题,我们以当前字符为中心往两边扩散的时候,先要判断和他挨着的有没有相同的字符,如果有,则跳过继续判断下一个,
根据这个思路,我们来写下代码:
class Solution {
public:
string longestPalindrome(string s) {
// 获取字符串s的长度
int length = s.size();
// 设置回文子串起始位置和字串长度的初始值
int start = 0, maxlen = 0;
for(int i = 0; i < length; ){
// 判断剩余字串长度小于当前回文字串的长度,则直接跳出循环
if(length - i < maxlen / 2){
break;
}
int left = i, right = i;
// 过滤掉重复的字符
while(right < length - 1 && s[right + 1] == s[right]){
++right;
}
// 下次循环是直接从重复的下一个位置开始判断
i = right + 1;
// 往两边开始扩散,求回文字串长度
while(right < length -1 && left > 0 && s[left - 1] == s[right + 1]){
--left;
++right;
}
// 求出最长回文字串长度和起始位置
if(right - left + 1 > maxlen){
start = left;
maxlen = right - left + 1;
}
}
// 返回最长回文字串
return s.substr(start, maxlen);
}
};
版权声明:本文为weixin_43347550原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。