题解 | 最长回文子串-中心扩散法-0528

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        """
        中心扩散法： 
        从中间拓展延伸到首尾
         1. 遍历每个字符
         2. 遍历每个字符串以遍历到的字符为中心
          字符串长度的区别分为两种： 当前中心为a 时候，奇数长度  baab 偶数长度  bab   
         3. 如果两边字符都是相同就是回文不断向两边拓展
         4. 比较回文长度取最大值
        """
        if not A:
            return 0
        if len(A)<2:
            return 1

        s=list(A)
        n=len(s)
        mx =1 
        for i in range(n):
            left=i
            right=i+1
            # 偶数遍历
            while left>=0 and right<=n-1:
                if s[left]==s[right]:
                    mx=max(mx,right -left+1)
                else:
                    break 
                left-=1
                right+=1
            # 奇数遍历
            left=i
            right=i
            while left>=0 and right<=n-1:
                #print(left,right)
                if s[left]==s[right]:
                    mx=max(mx,right -left+1)
                else:
                    break
                left-=1
                right+=1
            
        return mx 




    def getLongestPalindrome1(self , A: str) -> int:
        # write code here
        """
        暴力方法 
        通过用例数 25/26 超时  时间复杂度O（n^3）
        外层循环 i-n 遍历整个字符串
        内层循环： 设置 left =i  right 等于n-1 
          变写判断回文数的函数
         记录最大的回文串的左右 下标
        """
        s=list(A)
        n=len(s)
        mx_left=0
        mx_right=0
        def fun(s,left,right)->bool:
            while left<=right:
                if s[left]!=s[right]:
                    return False
                left+=1
                right-=1
            return True

        for i in range(n):
            for j in range(i,n):
                ret= fun(s,i,j)
                #print(ret)
                if ret:
                    if mx_right-mx_left < j-i:
                        mx_left=i
                        mx_right=j
                    
        ret="".join(s[mx_left:mx_right+1])
        return  len(ret)