最长回文子串

题目内容

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

示例 1：

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

示例 2：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring

题解一：中心扩展法

构建一个【从中心往两边扩散】的函数——扩散的条件是，不超出边界且扩散的两边的元素相等，函数返回【回文字符串】。
对给定的字符串每个位置进行遍历，并且判断找到的回文字符串长度，返回最长的字符串。

需要注意的是，如果回文字符串长度是奇数，那么该字符串中间的字符并不会有回文字符，比如“bab”，a 只出现一次，但是该字符串仍然是回文字符串，偶数长度则正好相反，如“baab”。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""

        for i in range(0, len(s)):
            a = self.findK(s, i, i) # 寻找长度是奇数的回文字符串
            b = self.findK(s, i, i+1) # 寻找长度是oushu 的回文字符串
			
			# 判断回文字符串长度
            if len(b) > len(a):
                if len(b) > len(res):
                    res = b
            else:
                if len(a) > len(res):
                    res = a

        return res

    def findK(self, s, left, right):
    	# 寻找回文字符串
        ans = ""
        while left >= 0 and right <= len(s) - 1 and s[left] == s[right]:
            if left == right: # 寻找奇数回文字符串时，一开始的字符要添加，并且因为 左指针等于右指针，所以添加一遍就可以
                ans = s[left]
            else:
                ans = s[left] + ans + s[right]
            left -= 1
            right += 1

        return ans
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
30

力扣通过的时间是912 ms

题解二：动态规划

该题解文字使用力扣题解作者_Breiman的题解

链接：https://leetcode.cn/problems/longest-palindromic-substring/solution/5-zui-chang-hui-wen-zi-chuan-dong-tai-gu-p7uk/

1. 定义状态：题目让我们求什么，就把什么设置为状态
   题目求s中最长的回文子串，那就判断所有子串是否为回文子串，选出最长的
   因此：dp[i][j]表示s[i:j+1]是否为回文子串（这里+1是为了构造闭区间）

2. 状态转移方程：对空间进行分类讨论（当前ij状态、过去ij状态 如何联合得到输出）
   当前ij状态：头尾必须相等（s[i]==s[j]）
   过去ij状态：去掉头尾之后还是一个回文（dp[i+1][j-1] is True）
   边界条件：只要是找过去ij状态的时候，就会涉及边界条件（即超出边界情况处理）
   当i==j时一定是回文
   j-1-(i+1)<=0,即j-i<=2时，只要当s[i]==s[j]时就是回文，不用判断dp[i+1][j-1]
   dp[i][j] 为截取的子串

3. 输出内容：每次发现新回文都比较一下长度，记录i与长度

class Solution:
    def longestPalindrome(self, s: str) -> str:
        max_length = 0
        res = ""

        length = len(s)
        
        # n * n 的矩阵，元素全是 False
        dp = [[False] * length for i in range(length)]

        if length == 1:
            return s

        for right in range(length):
            for left in range(right+1):
                index = right - left + 1
                if index == 1:
                    dp[left][right] = True
                elif index == 2:
                    dp[left][right] = (s[left] == s[right])
                else:
                    dp[left][right] = (s[left] == s[right] and dp[left+1][right-1])

                if dp[left][right]:
                    if max_length < index:
                        max_length = index
                        res = s[left: right+1] 

        return res
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

力扣通过的时间是4924 ms