[数据结构与算法]LeetCode：5. 最长回文子串————中等

题目

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

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

示例 2：
输入：s = "cbbd"
输出："bb"

示例 3：
输入：s = "a"
输出："a"

示例 4：
输入：s = "ac"
输出："a"
 

提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

解题思路

• 动态规划。
• 状态定义：dp[i][j]表示字串的i位置到j位置是回文子串。
• 状态转移方程：dp[i][j] = (s[i] == s[j] ) and dp[i + 1][j -1]
• 状态初始化。

Code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2: return s
        max_len = 1  # 初始长度为1
        begin = 0  # 记录起始位置
        # dp[i][j] 表示 s[i..j] 是否是回文串
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True  # 对角线的元素一定为True

        # 递推开始
        # 先枚举子串长度
        for l in range(2,n+1):
            for i in range(n):
                r = l + i - 1
                if r >= n:
                    break
                if s[i] != s[r]:
                    dp[i][r] = False
                else:
                    if r - i < 3:
                        dp[i][r] = True
                    else:
                        dp[i][r] = dp[i + 1][r - 1]
                if dp[i][r] and r -i + 1 > max_len:
                    max_len = r - i + 1
                    begin = i
        return s[begin:begin + max_len]

运行结果