题目：

原题链接： https://leetcode-cn.com/problems/longest-palindromic-substring/

 

解题思路：

官方题解一共有五种方法，比对自己实现的方式，和第四种“中心扩展法”相同

思路如下：

回文字符串的中心，有两种情况：

1. 某个字符(n个)
2. 两个字符中间(n - 1个)

所以，一共有2n - 1个可能

对每个中心，进行左右扩展，直到左右两边字符不相同，结束扩展，并保存最大字符串长度

时间复杂度为

 

ps. 还有种更高效的算法，能搞达到O(n)的时间复杂度，叫马拉车算法: https://oi-wiki.org/string/manacher/

强烈建议查看并理解这个算法，官方也是这么建议的

这里我就不多说了，肯定没wiki上解释的好

 

代码实现：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def get_max_len(s, low, high):
            if len(s) == 0:
                return 0
            
            while low >= 0 and high < len(s) and s[low] == s[high]:
                low -= 1
                high += 1
                
            return high - low - 1
        
        if len(s) == 0:
            return ''
        
        start, end = 0, 0
        for i in range(0, len(s)):
            len1 = get_max_len(s, i, i)
            len2 = get_max_len(s, i, i + 1)
            max_len = max(len1, len2)
            if max_len > end - start:
                start = i - (max_len - 1) // 2
                end = i + max_len // 2
                
        return s[start:end + 1]