5. 最长回文子串(双指针扩展遍历)
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
题解：
1.一个字符串 s
2.找最长的回文子串
3.与前几题不同，这次要返回最长回文串内容
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
解题思路：奇偶数回文串双指针扩展
-
已经给了全部字符串，返回的连续子串一定是该串的子集或全集
-
考虑两种回文类型：奇回文如aba,偶回文或对偶回文如abba
-
从首字符开始向两边扩展，扩展中心指针不断后移到尾
-
以当前位置字符开始用左右指针向两边比较对应字符是否相同，相同继续扩展至边界跳出；不相同则不再扩展
-
根据左右指针位置计算回文串长度，并与记录最大长度变量取最大值
C/C++题解：
class Solution {
public:
int len = 0; //记录最长回文的长度
int begin = 0; // 记录最长回文的起始位置
string longestPalindrome(string s) {
if (s.length() < 2) return s;
for (int i = 0; i < s.length(); i++) {
expand(s, i, i); //奇回文 例如 cbabd
expand(s, i, i + 1); }//偶数回文 例如abbccd
return s.substr(begin, len);}
void expand(string chs, int L, int R) {
while (L >= 0 && R < chs.length() && chs[L] == chs[R]) { // 往两边扩展
L--;
R++;}//左右指针不在长度范围内或不相等时跳出，此时R，L在回文串外两端
//回文串长度是R-1 -(L+1) + 1 = R - L - 1
// 比如 aabac, 此时L = 0, R = 4, 长度为 R - L - 1，也就是中间的3
if (R - L - 1 > len) {
len = R - L - 1;
begin = L + 1;}}};
Debug结果：
Java题解：
class Solution {
private int len = 0; //记录最长回文的长度
private int begin = 0; // 记录最长回文的起始位置
public String longestPalindrome(String s) {
if (s == null || s.length() < 2) return s;
char[] chs = s.toCharArray();
for (int i = 0; i < chs.length; i++) {
expand(chs, i, i); //奇回文 例如 cbabd
expand(chs, i, i + 1); }//偶数回文 例如abbccd
return s.substring(begin, begin + len);}
private void expand(char[] chs, int L, int R) {
while (L >= 0 && R < chs.length && chs[L] == chs[R]) { // 往两边扩展
L--;
R++;}//左右指针不在长度范围内或不相等时跳出，此时R，L在回文串外两端
//回文串长度是R-1 -(L+1) + 1 = R - L - 1
// 比如 aabac, 此时L = 0, R = 4, 长度为 R - L - 1，也就是中间的3
if (R - L - 1 > len) {
len = R - L - 1;
begin = L + 1;}}}
Debug结果：
Python题解：
class Solution(object):
global leng #记录最长回文的长度
global begin #记录最长回文的起始位置
def longestPalindrome(self, s):
""":type s: str :rtype: str"""
self.leng = 0
self.begin = 0
def expand(s, L, R):#往两边扩展
while L >= 0 and R < len(s) and s[L] == s[R]:
L -= 1
R += 1
if R - L - 1 > self.leng:
self.leng = R - L - 1
self.begin = L + 1
if len(s) < 2: return s
# leng = 0 #记录最长回文的长度
# begin = 0 #记录最长回文的起始位置
for i in range(len(s)):
expand(s, i, i) #奇回文例如 cbabd
expand(s, i, i + 1) #偶数回文例如abbccd
return s[self.begin:self.begin+self.leng]
Debug结果：
更多题解请移步公众号免费获取