Luxin's Blog

Code & Life

最长回文子串

发表于 更新于 分类于

题目描述

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

示例

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

提示

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

解题思路

这是一道经典的字符串处理问题，可以使用动态规划来解决。

核心思想

定义 dp[i][j] 表示：子串 s[i:j+1] 是否为回文子串。

从长度为 1 的子串开始，逐步扩展到长度为 n 的子串。

初始状态

  • dp[i][i] = true：表示单个字符都是回文子串

状态转移方程

当 s[i] == s[j] 时：

  • 若 j - i < 3（即子串长度为 2 或 3），则 dp[i][j] = true
  • 否则，dp[i][j] = dp[i+1][j-1]

用公式表示：

$$
dp[i][j] =
\begin{cases}
\text{true} & \text{当 } s[i] = s[j] \text{ 且 } j - i < 3 \
dp[i+1][j-1] & \text{当 } s[i] = s[j] \text{ 且 } j - i \geq 3 \
\text{false} & \text{当 } s[i] \neq s[j]
\end{cases}
$$

遍历顺序

  • 外层循环：子串长度 length 从 2 到 n
  • 内层循环：起始位置 i 从 0 到 n - length
  • 结束位置 j = i + length - 1

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True

        max_len = 1
        begin = 0

        for length in range(2, n + 1):
            for i in range(0, n):
                j = i + length - 1
                if j >= n:
                    break

                if s[i] != s[j]:
                    dp[i][j] = False
                else:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]

                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i

        return s[begin:begin + max_len]