一：最长回文子串（leetcode 5）

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

思路一：

暴力遍历字符串，得到所有符合结果，比较之后求出最长字符串，这种方法最好想到，但是会超时

C++：

class Solution {
public:string longestPalindrome(string s) {string res="";//存放结果string temp="";//存放子串for(int i=0;i<s.length();i++){for(int j=i;j<s.length();j++){temp=temp+s[j];string tem=temp;//tem存放子串反转结果std::reverse(tem.begin(),tem.end());//反转if(temp==tem)res=res.length()>temp.length()?res:temp;}temp="";}return res;}
};

思路二：

双指针中心扩散法，设置左右指针start，end，遍历字符串，以当前遍历的位置向左右两端扩散，并判断start值是否=end的值，如果等于则继续判断，直至不等于，返回start和end指针之间的字符串长度，并判断是否为最长回文子串，最后输出start和end指针之间的字符即可

C++：

class Solution {
public:string longestPalindrome(string s) {int len=s.size();if(len==0||len==1)return s;int start=0;//记录回文子串起始位置int end=0;//记录回文子串终止位置int mlen=0;//记录最大回文子串的长度for(int i=0;i<len;i++){int len1=expendaroundcenter(s,i,i);//一个元素为中心int len2=expendaroundcenter(s,i,i+1);//两个元素为中心mlen=max(max(len1,len2),mlen);if(mlen>end-start+1){start=i-(mlen-1)/2;end=i+mlen/2;}}return s.substr(start,mlen);//该函数的意思是获取从start开始长度为mlen长度的字符串}
private:int expendaroundcenter(string s,int left,int right)//计算以left和right为中心的回文串长度{int L=left;int R=right;while(L>=0 && R<s.length() && s[R]==s[L]){L--;R++;}return R-L-1;}
};

Python：

class Solution(object):def longestPalindrome(self, s):def palindrome(s, l, r):while l >= 0 and r < len(s) and s[l] == s[r]:l -= 1r += 1return s[l+1:r]res = ''for i in range(len(s)):sub1 = palindrome(s, i, i)sub2 = palindrome(s, i, i+1)if len(sub1) > len(res):res = sub1  if len(sub2) > len(res):res = sub2 else :resreturn res

复杂度分析

时间复杂度：O(n^2)

空间复杂度：O(1)

二：回文子串（leetcode 647）

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

方法：双指针中心扩散法，即问题一的法二

C++：

class Solution {
public:int countSubstrings(string s) {int result = 0;for (int i = 0; i < s.size(); i++) {result += extend(s, i, i, s.size()); // 以i为中心result += extend(s, i, i + 1, s.size()); // 以i和i+1为中心}return result;}int extend(const string& s, int i, int j, int n) {int res = 0;while (i >= 0 && j < n && s[i] == s[j]) {i--;j++;res++;}return res;}
};

Python：

class Solution:def countSubstrings(self, s: str) -> int:result = 0for i in range(len(s)):result += self.extend(s, i, i, len(s)) #以i为中心result += self.extend(s, i, i+1, len(s)) #以i和i+1为中心return resultdef extend(self, s, i, j, n):res = 0while i >= 0 and j < n and s[i] == s[j]:i -= 1j += 1res += 1return res