leetcode-5-最长回文子串

题目

https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=dynamic-programming

题解

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n==1:
            return s

        # res_left, res_right 左包含，右不包含
        res_left, res_right = 0, 0

        for i in range(1,2*n):
            if i%2==1:
                left = (i-1)//2
                right = (i+1)//2
            else:
                left = i//2-1
                right = i//2+1
            while left>=0 and right<n:
                if s[left] == s[right]:
                    left -= 1
                    right += 1
                else:
                    break
            if right-left-1 >  res_right-res_left:
                # left回一步； right本应回一步，但是不包含所以不用回了
                res_left, res_right = left+1,right
        return s[res_left:res_right]