📕题干
中等
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
📖题解
法一
💻代码
class Solution:
def longestPalindrome(self, s: str) -> str:
a = ""
for i in range(len(s),0,-1):
for j in range(len(s)-i+1):
a = s[j:j+i]
x = 0
while a==a[::-1]:
return a🤔思路
直接暴力求解，从最长子串开始，逐个判断是否构成回文。
❗ 注意
本题做出来不难，但显然这样的思路仅仅能停留在做出来，显然执行用时太长。时间复杂度达到了O(n^3)，因而要更进一步改进算法。
法二
💻代码
class Solution:
def longestPalindrome(self, s: str) -> str:
longest = ""
for i in range(len(s)):
l = min(i,len(s)-i-1)
j = 0
result1,result2 = "",""
while j <= l:
a = s[i-j:i+j+1]
if a == a[::-1]:
result1 = a
j += 1
else:
break
l = min(i,len(s)-i)
j = 0
while j <= l:
a = s[i-j:i+j]
if a == a[::-1]:
result2 = a
j += 1
else:
break
if len(result1) > len(longest):
longest = result1
if len(result2) > len(longest):
longest = result2
return longest🤔思路
由于回文子串有个特性，即若abcdcba是回文，则bcdcb一定也是回文。换句话说可以从短回文入手，再扩大范围，得到最长回文。比较根据字符串中各个字符产生的子串长度，得到最长的回文子串。
❗ 注意
此方法的执行时间明显下降，时间复杂度达到了O(n^2)，但显然这个程度的时间还是过长，要进一步改进。
法三
💻代码
class Solution:
def longestPalindrome(self, s: str) -> str:
longest = ""
def ifsidessame(left:int,right:int,result:str) -> str:
if left < 0 or right >= len(s):
return result
elif left == right:
result = s[left]
return ifsidessame(left-1,right+1,result)
elif s[left] == s[right]:
result = s[left]+result+s[right]
return ifsidessame(left-1,right+1,result)
else:
return result
for i in range(len(s)):
result1 = ifsidessame(i,i,"")
result2 = ifsidessame(i,i+1,"")
if len(result1) > len(longest):
longest = result1
if len(result2) > len(longest):
longest = result2
return longest🤔思路
我对法二中的拓展回文方法进一步优化，定义了ifsidesame函数，用来处理得到指定一个（奇数长度回文）或两个（偶数长度回文）字符时对应的最长回文，此时再遍历字符串，运用此函数便能对每一个字符返回最长子串，从而得出结果。
❗ 注意
此方法的执行时间任有下降，时间复杂度为O(n^2)，但仍然不足。原因在于只是对原算法的优化，而要明显降低执行时间，需要重构。
法四
💻代码
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) < 2:
return s
def ifsidesame(left: int, right: int) -> str:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left+1:right]
longest = ""
for i in range(len(s)):
result1 = ifsidesame(i, i)
result2 = ifsidesame(i, i + 1)
longest = max(longest, result1, result2, key=len)
return longest🤔思路
法三中采用递归的方式，而在法四中采用了迭代的方式。法三对字符串采用拼接，法四对字符串采用切片。这样的调整，可以降低执行时间。
📌没有了吗
到这里看似已经得到了最优解了，因为此时的执行时间在Leetcode的分布上已经很前面了。但是这就结束了吗❓
法五
💻代码
class Solution:
def longestPalindrome(self, s: str) -> str:
t = '#'.join(f'^{s}$')
n = len(t)
p = [0] * n
center = right = 0
for i in range(1, n - 1):
p[i] = (right > i) and min(right - i, p[2 * center - i])
while t[i + p[i] + 1] == t[i - p[i] - 1]:
p[i] += 1
if i + p[i] > right:
center, right = i, i + p[i]
max_len, center_index = max((n, i) for i, n in enumerate(p))
start = (center_index - max_len) // 2
return s[start: start + max_len]
执行用时：84ms 消耗内存：16.57MB
🤔思路
在上述方法中，都涉及到了奇数回文串和偶数回文串的问题，为了统一解决方法，可以采用插入额外字符，如法五中的‘#’，并且通过'^'和'$'来标记原字符串的边界。
用p[]来保存对应字符的回文半径，初始化center中心和right右边界。
在遍历过程中，能发现当i在right左侧时，即i < right，（i > center）恒成立。可以由对称性可知，在半径小于right-i时，此时i对应的回文串，应当与i'一致，由于实际半径p[i']可能大于或者小于right-i，所以可以取两者最小值作为预处理的p[i]。
之后同之前的方法一样，对单个字符串在已有的p[i]基础上拓展出最长的回文串。由于遍历是从左至右，只有当下一个i的最右边界超过了已有的右边界，才能包含更多的未遍历数。便只需更新此时的center和right，而不必次次更新。
最终遍历得到p[]中最大的值与索引，最终计算出对应切片，返回。时间复杂度为O(n)
💡要点
- 代码中第8行预处理格外重要，在测试下，没有经过预处理的代码块在Leetcode中实际执行时间为626ms，差距巨大。
- 代码中第11行仅保存超右边界数值，在测试下，没有此行的代码块在Leetcode中实际执行时间为179ms，翻了一番。
- 此代码中运用了Manacher’s Algorithm算法，此算法是用来查找一个字符串的最长回文子串的线性方法，可以使正常时间复杂度为O(n^2)的任务变为O(n)。
