题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入： s = "babad"
输出： "bab"
解释： "aba" 同样是符合题意的答案。
示例 2：
输入： s = "cbbd"
输出： "bb"
示例 3：
输入： s = "a"
输出： "a"
示例 4：
输入： s = "ac"
输出： "a"
提示
1 <= s.length <= 1000s仅由数字和英文字母（大写和/或小写）组成
解题思路
1.暴力法
暴力法始终是最简单的一种解法，但是速度方面就不尽人意。两层 for 循环遍历所有情况，找出最大的回文子串。代码提交时显示超时。这就很难受了！
class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ length = len(s) # 将首字符作为max_str的初始值 max_str = s[0] for i in range(length - 1): for j in range(i + 1, length): # 如果s[i: j + 1]是回文子串并且长度大于len(max_str)，就将其替换 if s[i: j + 1] == s[i: j + 1][::-1] and j - i + 1 > len(max_str): max_str = s[i: j + 1] return max_str 复制代码
时间复杂度：O(n³)
空间复杂度：O(1）
2.中心扩散法
根据回文串的对称性，我们可以指定它的中心进行循环，每次判断左右字符是否相等即可。
class Solution(object): def expandAroundCenter(self, s, left, right): max_len = 0 # 退出条件：越界 while left >= 0 and right < len(s): if s[left] == s[right]: left -= 1 right += 1 else: break return right - left - 1 def longestPalindrome(self, s): """ :type s: str :rtype: str """ rst = s[0] # 遍历中心点 for i in range(len(s) - 1): # 通过expandAroundCenter方法获取最大回文串长度 # 奇数时，left = right = i odd_len = self.expandAroundCenter(s, i, i) # 偶数时，left = i，right = i + 1 even_len = self.expandAroundCenter(s, i, i + 1) #获取最大len max_len = max(odd_len, even_len) if max_len > len(rst): # 获取回文串起始下标 begin = i - (max_len - 1) // 2 rst = s[begin: begin + max_len] return rst 复制代码
时间复杂度：O(n²)
空间复杂度：O(1）
今日打卡完成，目前进度 8/200。
