回文子串是正反读相同的连续子串，常用中心扩展法在O(n²)时间内找出最长回文子串；也可通过动态规划或Manacher算法优化处理。
判断和找回文子串是字符串处理中的常见问题。回文子串指的是正着读和反着读都一样的连续子串，比如 “aba” 或 “abba”。在 python 中有几种有效的方法可以找出一个字符串中所有的回文子串，或者最长的回文子串。
1. 中心扩展法
回文串的特征是以某个位置或两个位置之间的空隙为中心，向两边对称扩展。我们可以枚举每个可能的中心点，然后向左右扩展，判断是否构成回文。
这种方法的时间复杂度为 O(n²)，空间复杂度为 O(1)，适合找最长回文子串。
立即学习“Python免费学习笔记（深入）”；
def longest_palindrome(s): if not s: return "" <pre class='brush:python;toolbar:false;'>start = 0 max_len = 1 def expand_around_center(left, right): while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 # 返回长度（注意边界） return right - left - 1 for i in range(len(s)): len1 = expand_around_center(i, i) # 奇数长度回文 len2 = expand_around_center(i, i+1) # 偶数长度回文 current_max = max(len1, len2) if current_max > max_len: max_len = current_max start = i - (current_max - 1) // 2 return s[start:start + max_len]
调用示例：
print(longest_palindrome("babad")) # 输出："bab" 或 "aba" print(longest_palindrome("cbbd")) # 输出："bb"
2. 找出所有回文子串
如果目标是找出字符串中所有的回文子串，可以在中心扩展的基础上稍作修改，收集每一个找到的回文串。
立即学习“Python免费学习笔记（深入）”；
def find_all_palindromes(s): palindromes = set() # 使用集合避免重复 <pre class='brush:python;toolbar:false;'>def expand_and_add(left, right): while left >= 0 and right < len(s) and s[left] == s[right]: palindromes.add(s[left:right+1]) left -= 1 right += 1 for i in range(len(s)): expand_and_add(i, i) # 奇数长度 expand_and_add(i, i+1) # 偶数长度 return list(palindromes)
示例：
print(find_all_palindromes("aabbaa")) # 输出可能包含："a", "b", "aa", "bb", "abba", "aabbaa" 等
3. 动态规划方法
也可以使用动态规划来解决最长回文子串问题。定义 dp[i][j] 表示从索引 i 到 j 的子串是否为回文。
状态转移方程：
- 如果 s[i] == s[j]，且内部子串 dp[i+1][j-1] 是回文，或者子串长度 ≤ 2，则 dp[i][j] = True
时间复杂度 O(n²)，空间复杂度 O(n²)。
立即学习“Python免费学习笔记（深入）”；
def longest_palindrome_dp(s): n = len(s) if n == 0: return "" <pre class='brush:python;toolbar:false;'>dp = [[False] * n for _ in range(n)] start = 0 max_len = 1 # 单个字符都是回文 for i in range(n): dp[i][i] = True # 检查长度为2的子串 for i in range(n - 1): if s[i] == s[i+1]: dp[i][i+1] = True start = i max_len = 2 # 检查长度大于2的子串 for length in range(3, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j] and dp[i+1][j-1]: dp[i][j] = True start = i max_len = length return s[start:start + max_len]
4. 使用 Manacher 算法（进阶）
Manacher 算法可以在 O(n) 时间内找出最长回文子串，适合处理大规模数据。实现较为复杂，一般面试中了解即可。
其核心思想是利用回文的对称性，避免重复计算。
基本上就这些常用方法。中心扩展法最直观、易理解，推荐日常使用。动态规划逻辑清晰但耗空间，而 Manacher 是性能最优解。根据实际需求选择合适的方法即可。