[LeetCode] 5. 最长回文子串 (Longest Palindromic Substring)

发表于 分类于

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。

解题思路

方法一：中心扩展法

以每个字符（或两个字符的间隙）为中心向两边扩展，检查是否构成回文。

  • 时间复杂度： O(n^2)
  • 空间复杂度： O(1)

方法二：动态规划

定义 dp[i][j] 表示 s[i..j] 是否为回文。状态转移方程：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]。

  • 时间复杂度： O(n^2)
  • 空间复杂度： O(n^2)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s

        start, max_len = 0, 1

        def expand(l, r):
            nonlocal start, max_len
            while l >= 0 and r < n and s[l] == s[r]:
                if r - l + 1 > max_len:
                    start = l
                    max_len = r - l + 1
                l -= 1
                r += 1

        for i in range(n):
            expand(i, i)      # 奇数长度
            expand(i, i + 1)  # 偶数长度

        return s[start:start + max_len]

总结

回文问题的经典解法有两种：中心扩展和动态规划。中心扩展法空间更优，推荐优先使用。