Leetcode刷题5--- 最长回文子串 Python

Leetcode刷题5— 最长回文子串 Python

问题描述

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

示例

示例 1:
“”"
输入: s = “babad”
输出: “bab”
解释: “aba” 同样是符合题意的答案。
“”"

示例 2:
“”"
输入: s = “cbbd”
输出: “bb”
“”"

提示

• 1 ≤ s . l e n g t h ≤ 1000 1 \leq s.length \leq 1000 1≤s.length≤1000
• s 仅由数字和英文字母组成。

方法一：动态规划

思路：

1. 定义 dp[i][j] 表示字符串 s 的子串 s[i:j] 是否是回文子串。
2. 状态转移方程：
   • 如果 s[i] == s[j] 且 j - i <= 2，则 dp[i][j] = true。
   • 如果 s[i] == s[j] 且 j - i > 2，则 dp[i][j] = dp[i+1][j-1]。
3. 遍历所有子串，记录最长的回文子串。

代码实现：

def longestPalindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s

    dp = [[False] * n for _ in range(n)]
    start, max_length = 0, 0

    for j in range(n):
        for i in range(j + 1):
            if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
                dp[i][j] = True
                if j - i + 1 > max_length:
                    start = i
                    max_length = j - i + 1

    return s[start:start + max_length]

方法二：中心扩展法

思路：

1. 回文串的中心有两种情况：
   • 单个字符为中心；
   • 两个字符之间为中心。
2. 从每个可能的中心向外扩展，找到最大长度的回文子串。

代码实现：

def longestPalindrome(s: str) -> str:
    def expand_around_center(left: int, right: int) -> str:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]

    max_palindrome = ""
    for i in range(len(s)):
        # 单中心扩展
        palindrome1 = expand_around_center(i, i)
        # 双中心扩展
        palindrome2 = expand_around_center(i, i + 1)
        # 更新最长回文子串
        max_palindrome = max(max_palindrome, palindrome1, palindrome2, key=len)

    return max_palindrome
"""