链接

https://leetcode-cn.com/problems/longest-palindromic-substring/

前言

题目

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

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

示例2：

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

示例3：

输入：s = "a"
输出："a"

示例4：

输入：s = "ac"
输出："a"

关键

思路1

动态规划
dp[i][j]表示位置i到j的子串是否为回文串
i到j的子串为回文串需满足：
- s[i]=s[j]
- dp[i+1][j-1]为回文串
双遍历首先在长度n遍历右边位置j，然后在j的范围内遍历左边位置i
回文子串的长度span有3种情况：
- span=1时，直接就是回文串
- span=2时，需满足s[i]=s[j]
- span>2即剩余其他情况时，需满足s[i]=s[j]同时 dp[i+1][j-1]为True

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        dp = [[False]*n for _ in range(n)]
        start = 0
        max_len = 1
        for j in range(n):
            for i in range(j+1):
                span = j-i+1
                if span==1:
                    dp[i][j] = True
                elif span==2:
                    dp[i][j] = s[i]==s[j]
                else:
                    dp[i][j] = dp[i+1][j-1] and s[i]==s[j]
                if dp[i][j]:
                    if span>max_len:                
                        max_len=span
                        start = i
        return s[start:start+max_len]