最长回文子串（HJ16）

最长回文子串

题目描述

https://www.nowcoder.com/share/jump/5832603751775720167173

给定一个仅包含小写字母的字符串，求其最长回文子串的长度。

• 回文串指正读和反读都相同的字符串
• 子串为原字符串中连续的一段字符

示例

输入：

cdabbacc

输出：

4

解释：最长回文子串为 “abba”

输入：

abbacde

输出：

4

解释：最长回文子串为 “abba”

解题思路

中心扩展法

回文串具有中心对称的特性。我们可以枚举每个可能的中心点，然后向两边扩展，直到不再是回文为止。

关键点： - 奇数长度回文（如 “aba”）：中心是单个字符 - 偶数长度回文（如 “abba”）：中心是两个字符之间

因此每个位置需要扩展两次： 1. expand(i, i) - 以 i 为中心（奇数长度） 2. expand(i, i+1) - 以 i 和 i+1 之间为中心（偶数长度）

代码实现

中心扩展法

s = input().strip()

res = ""

def expand(l, r):
    """从中心 (l, r) 向两边扩展，返回最长回文子串"""
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    return s[l + 1: r]

for i in range(len(s)):
    res = max(res, expand(i, i), key=len)     # 奇数长度回文
    res = max(res, expand(i, i + 1), key=len) # 偶数长度回文

print(len(res))

代码解析

expand(l, r) 函数

初始:    l = i, r = i          l = i, r = i+1
         a b a                  a b b a
            ↑                      ↑ ↑
           中心                  中心

扩展:   l--, r++               l--, r++

• while l >= 0 and r < len(s)：边界检查
• s[l] == s[r]：回文判断，两边字符相等则继续扩展
• s[l + 1: r]：循环结束时 l 和 r 都越界了一步，需要修正

max(res, expand(i, i), key=len) 解析

部分	含义
max()	Python 内置函数，返回最大值
res	当前找到的最长结果
expand(i, i)	从中心 i 向两边扩展查找回文串
key=len	比较长度作为判断标准

选择 res 和 expand(i, i) 中长度更长的那个作为新的 res。

时间复杂度

• O(n²)：n 个中心点，每个中心点最多扩展 n 次

空间复杂度

• O(1)：只使用常数额外空间（不含输入和输出）