Force KouTi (5), the longest text string back

最长回文子串

题目内容

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

示例 1：

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

示例 2：

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

提示：

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

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

题解一：中心扩展法

构建一个【Spread from the center to both sides】的函数——The conditions for diffusion are,The elements are equal on both sides of the boundary and spread,函数返回【回文字符串】.
Iterates over each position of the given string,And judge the length of the found palindrome string,返回最长的字符串.

需要注意的是,If the palindrome string length is odd,Then the characters in the middle of the string will not have palindrome characters,比如“bab”,a 只出现一次,But the string is still a palindrome,The opposite is true for even lengths,如“baab”.

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

        for i in range(0, len(s)):
            a = self.findK(s, i, i) # Finds a palindrome string of odd length
            b = self.findK(s, i, i+1) # looking for length isoushu 的回文字符串
			
			# Determines the length of the palindrome string
            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: # When looking for odd palindrome strings,The first character to be added,并且因为 The left pointer is equal to the right pointer,So just add it again
                ans = s[left]
            else:
                ans = s[left] + ans + s[right]
            left -= 1
            right += 1

        return ans

The time for the force buckle to pass is912 ms

题解二：动态规划

The text of the problem solution uses the force deduction problem to solve the author_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

The time for the force buckle to pass is4924 ms