5.最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/5zui-chang-hui-wen-zi-chuan-hui-wen-chan-z3yj/

难度：中等

题目：

给你一个字符串 s，找到 s 中最长的回文子串。

示例：

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"

示例 3：
输入：s = "a"
输出："a"

示例 4：
输入：s = "ac"
输出："a"

分析

这道题看似麻烦，但仔细考虑回文子串只有两种情况：

1. 奇数回文，即 aba
2. 偶数回文，即 abba

那么我们只需要循环字符串的每一个index，当满足一下条件时，从中心向两边扩展：

1. left >= 0
2. right < len(s)
3. 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

欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。

我的个人博客：https://qingfengpython.cn

力扣解题合集：https://github.com/BreezePython/AlgorithmMarkdown