5.最长回文子串
难度：中等
题目：
给你一个字符串 s，找到 s 中最长的回文子串。
示例：
示例 1： 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 示例 2： 输入：s = "cbbd" 输出："bb" 示例 3： 输入：s = "a" 输出："a" 示例 4： 输入：s = "ac" 输出："a"
分析
这道题看似麻烦，但仔细考虑回文子串只有两种情况：
- 奇数回文，即 aba
- 偶数回文，即 abba
那么我们只需要循环字符串的每一个index，当满足一下条件时，从中心向两边扩展：
- left >= 0
- right < len(s)
- s[left] == s[right]
对于第三个条件，存在奇数回文和偶数回文的判断：
- 奇数回文时，我们初始left == right
- 偶数回文时，我们初始化right == left + 1
根据这两种情况进行遍历，最终即可获取结果。具体代码如下。
解题：
class Solution: def longestPalindrome(self, s): ln = len(s) # s为空或者s为自己本身的情况 if ln < 2: return s ret = '' def finder(left, right): nonlocal ret while left >= 0 and right < ln and s[left] == s[right]: left -= 1 right += 1 ret = s[left + 1:right] if right - left - 1 > len(ret) else ret for i in range(ln ): finder(i, i) finder(i, i + 1) return ret
