点击查看题目详情

1. 中心扩散法

• 思路：

遍历字符串，以每个字符为中心点向两边扩散，如果遇到不一样的就跳出循环。以此类推，最后截取最大回文串返回。

• 细节

字符个数不一定都是奇数。当个数是偶数的是时候，我们可以“忽略”部分重复值。

这是因为：

我们把单个字符看作回文串，比如a；并且多个重复字符也看作回文串，比如aaa。

那么对于abba这种偶数的回文串来说，用普通的扩散方法肯定是不对的，但是我们可以跳过bb那一段，因为已经默认了是回文串。

所以对于上面的问题，我们以当前字符为中心往两边扩散的时候，先要判断和他挨着的有没有相同的字符，如果有，则直接跳过。

那么对于abba来说，a默认不是回文，不做判断；所以从b开始，此时首先判断其右边有无重复值，判断出有，所以跳过b来到a。注意此时的跳过指的是i跳过，意思就是说剩余子串判断，是跳过了重复值的。

而对于现在的b为起点来说，判断的条件是s[right] == s[right+1]，所以此时的right是在第二个b上的，也就是说i是跟着right走，判断出是回文、重复，下一轮判断剩余子串就没必要再从起点的下一字符开始了，就直接从边界的下一个开始。 所以i不是使用++来迭代的。

还有一个注意的点，当剩余的子串大小不够maxsize大时，可以直接跳出循环了，因为即使它是回文串，也不够maxsize大。

class Solution {
public:string longestPalindrome(string s) {if(s.size() < 2){return s;}int maxsize = 0, start = 0;//长度最大值和字符串起始位置(截取字符串)for(int i = 0;i < s.size();){//若不满足长度要求，提前退出//如果剩余子串个数不够，直接退出，因为即使它是回文串，个数也没有maxsize的多//size-i代表的是起点，也就是剩余子串的中间点，说明size-i是一半//maxsize/2代表的是目前最长子串的一半//所以相当于一半和一半比较if(s.size()-i <= maxsize/2)break;int right = i;int left = i;//跳过重复值while(right < s.size()-1 && (s[right+1] == s[right])){++right;}i = right+1;//迭代i，从right的右边开始//left为0的时候，也就是刚开始的时候不做判断while(right < s.size()-1 && left > 0 && (s[right+1] == s[left-1])){++right;--left;}//停止循环，此时的左右边界正好在边界值上if(right-left+1 > maxsize){start = left;//记录下此时的最长子串的起点，最后直接切割maxsize = right-left+1;}}//string substr (size_t pos = 0, size_t len = npos) const;return s.substr(start,maxsize);}
};

运行结果：

2. 暴力解法

通俗易懂，就是每个字符不断向右扩大区间分别去比较是否回文：

class Solution {
public:string longestPalindrome(string s) {if(s.size()<2){return s;}int start = 0,maxsize = 0;for(int i = 0;i < s.size()-1;i++){for(int j = i;j < s.size();j++){//j-i是边界，是剩余字符的总长度，而不是一半if(j - i < maxsize){continue;}if(isPalindrome(s,i,j)){if(maxsize < j-i+1){start = i;maxsize = j-i+1;}}}}return s.substr(start,maxsize);}bool isPalindrome(string& s,int left, int right){while(left < right){if(s[left++] != s[right--]){return false;}}return true;}
};

运行结果肯定会比第一种方法慢：