Python最长回文子串问题

class Solution:
    def longestPalindrome(self, s):
        if (len(s) < 2):
            return s
        start = 0  #记录最长回文子串开始的位置
        maxLen = 0 #记录最长回文子串的长度
        for i in range(len(s) - 1):
            for j in range(i,len(s)):#j从i开始，不从i+1开始，s=‘ac'就能选第一个‘a'
                # 法一：截取所有子串，然后在逐个判断是否是回文的
                # 法二（优化）：截取所有子串，如果截取的子串小于等于之前遍历过的最大回文串，直接跳过。
                          # 因为截取的子串即使是回文串也不可能是最大的，所以不需要判断
                if (j - i < maxLen):
                    continue
                if self.isPalindrome(s, i, j) and  (maxLen < j - i + 1):
                # maxLen为最大长度时，后面maxLen<j-i+1 就为False,能保证截取最长回文字符串
                    start = i
                    maxLen = j - i + 1
        return s[start:start + maxLen]
 
    # 判断是否是回文串
    def isPalindrome(self,s,start,end):
        while (start < end) :
            if s[start] != s[end]:
                 return False
            start += 1
            end -= 1
        return True
 
s =   "ac"
S = Solution()
result = S.longestPalindrome(s)
print(result)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        #  判断空字符串的情况
        if (s == ""):
            return ""
        result = ""
        sSize = len(s)
        # 选择一个中心点，向两侧扩展
        for i in range(sSize):
            # 奇数组情况
            tmpStr = self.expandHelper(s, i, i)
            # 偶数组情况
            tmpStr2 = self.expandHelper(s, i, i + 1)
            if len(tmpStr) > len(result):
                result = tmpStr
            if len(tmpStr2) > len(result):
                result = tmpStr2
        return result
 
    def expandHelper(self,s,left,right):
        sSize = len(s)
        while (left >= 0 and right < sSize and s[left] == s[right]):
            left -= 1
            right += 1
        # 小心s[left] != s[right]
        return s[(left + 1) : right]
 
 
s = "aaaabad"
S = Solution()
result = S.longestPalindrome(s)
print(result)

class Solution:
    def longestPalindrome(self, s):
        n = len(s)
        if n < 2:
            return s
 
        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i..j] 是否是回文串
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
 
        # 递推开始
        # 先枚举子串长度
        for L in range(2, n + 1):
            # 枚举左边界，左边界的上限设置可以宽松一些
            for i in range(n):
                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右边界越界，就可以退出当前循环
                if j >= n:
                    break
 
                if s[i] != s[j]:
                    dp[i][j] = False
                else:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]#只有dp[0][4]是True,dp[1][3]还是True……,这才是真正的回文串
                        # dp[i][j] = True #假如s="abaa",s[0]=s[4], d[0][4]=True,就被认为是回文串，跳入下一个环节
 
                # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        return s[begin:begin + max_len]
 
 
s = "abaa"
S = Solution()
result = S.longestPalindrome(s)
print(result)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s :
            return ""
        res = ""
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        max_len = float("-inf")
        for i in range(n):
            for j in range(i + 1):
                if s[i] == s[j] and (i - j < 2 or dp[j + 1][i - 1]):
                    dp[j][i] = 1
                if dp[j][i] and  max_len < i + 1 - j:
                    res = s[j : i + 1]
                    max_len = i + 1 - j
        return res

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
       #中心扩展法，最直观的方法
        def center_spread(L: int, R: int) -> str:
            while 0 <= L and R < n and s[L]==s[R]:
                L -= 1
                R += 1
            return s[L+1 : R]

        res = s[0]
        max_len = 1

        for i in range(n):
            odd_str = center_spread(i, i)
            even_str = center_spread(i, i+1)
            
            if len(odd_str) > len(even_str):    #若长度为奇数的长
                if len(odd_str) > max_len:
                    max_len = len(odd_str)
                    res = odd_str
            else:                               #若长度为偶数的长
                if len(even_str) > max_len:
                    max_len = len(even_str)
                    res = even_str
        
        return res