最长回文子串：动态规划，中心扩展

给你一个字符串s，找到s中最长的 

回文 子串。 

示例 1：

输入：s = "babad"

输出："bab"

解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"

输出："bb"

提示：

• 1
• s 仅由数字和英文字母组成

动态规划

class Solution(object):
    def longestPalindrome(self, s):
        n = len(s)
        if n < 2:
            return s

        # 初始化一个 n x n 的 DP 表，dp[i][j] 表示 s[i:j+1] 是否为回文子串
        dp = [[False] * n for _ in range(n)]
        start = 0  # 最长回文子串的起始位置
        max_len = 1  # 最长回文子串的长度

        # 单个字符是回文
        for i in range(n):
            dp[i][i] = True

        # 填充 DP 表
        for length in range(2, n + 1):  # length 表示子串长度
            for i in range(n - length + 1):
                j = i + length - 1  # 计算子串的结束位置
                if s[i] == s[j]:
                    if length == 2:
                        dp[i][j] = True  # 两个相同字符的子串是回文
                    else:
                        dp[i][j] = dp[i + 1][j - 1]  # 依赖内部的子串是否为回文

                    # 如果找到更长的回文子串，更新结果
                    if dp[i][j] and length > max_len:
                        start = i
                        max_len = length

        # 返回最长回文子串
        return s[start:start + max_len]

中心扩展

def longestPalindrome(s: str) -> str:
    if len(s) == 0:
        return ""

    def expandAroundCenter(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]

    longest = ""
    for i in range(len(s)):
        # 考虑奇数长度回文
        odd_palindrome = expandAroundCenter(i, i)
        # 考虑偶数长度回文
        even_palindrome = expandAroundCenter(i, i + 1)
        
        # 取最长的回文子串
        longest = max(longest, odd_palindrome, even_palindrome, key=len)

    return longest

# 示例测试
s = "babad"
print(longestPalindrome(s))  # 输出 "bab" 或 "aba"