5. 最长回文子串

一、向右拓展

算法思路

• 你用res记录当前找到的最长回文子串。
• 每次遍历到s[i]时，尝试找到以s[i]结尾的、比当前res更长的回文子串。
  • 先尝试长度为len(res)+2（即起点i-len(res)-1）的子串，看是不是回文。
  • 如果不是，再试len(res)+1的子串（起点i-len(res)），看是不是回文。
• 每次找到更长的回文串就更新res。

class Solution:def longestPalindrome(self, s: str) -> str:res = ''for i in range(len(s)):start = max(i - len(res) -1, 0)temp = s[start: i+1]if temp == temp[::-1]:res = tempelse:temp = temp[1:]if temp == temp[::-1]:res = tempreturn res

复杂度分析

• 外层for循环 O(n)
• 内部切片和反转判断回文，最坏O(n)（每次检查的temp长度最大可能接近n）
• 最坏时间复杂度 O(n^2)
• 空间复杂度 O(n)（切片和反转的临时空间）

二、中心拓展

算法思路

• 对于每个位置 i，以其为中心，分别尝试两种情况：
  1. 以 i 为中心（奇数长度回文串）
  2. 以 i 和 i+1 为中心（偶数长度回文串）
• 对每种中心，向两边扩展，若左右字符相等，则回文长度增加。
• 每次扩展后，如果回文长度超过当前最长，则更新结果 res。

class Solution:def longestPalindrome(self, s: str) -> str:res = ''for i in range(len(s)):# 奇数长度l, r = i, iwhile l >= 0 and r < len(s) and s[l] == s[r]:if r - l + 1 > len(res):res = s[l:r+1]l -= 1r += 1# 偶数长度l, r = i, i+1while l >= 0 and r < len(s) and s[l] == s[r]:if r - l + 1 > len(res):res = s[l:r+1]l -= 1r += 1return res

复杂度分析

• 外层循环 O(n)
• 每次中心扩展，最坏O(n)（从中心扩展到两边的极限情况）
• 总体时间复杂度：O(n^2)
• 除了结果字符串和少量变量，空间复杂度：O(1)

优化代码：

把更新res的判断提前，减少写法重复：

这样奇偶合并成一段代码，逻辑更紧凑。

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