5. 最长回文子串-leetCode&python

1、题目
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

2、代码

class Solution(object):
        def longestPalindrome(self,s):
            """
            中心扩散法：以当前字符向两端扩散，找到最长子串。
            对于给定的字符串，遍历字符串中的每一个字符或每两个字符之间的空隙，将其作为回文子串的中心。
            对于每个可能的中心位置，从该位置向两侧扩展，直到不满足回文条件为止。这一过程需要维护两个指针，一个指向当前中心字符的左侧，另一个指向当前中心字符的右侧。
            在扩展的过程中，不断更新当前回文子串的起始和结束索引，以及当前回文子串的长度。
            遍历所有可能的中心位置，记录最长的回文子串的起始和结束索引，即可得到最长回文子串。
            """
            if len(s) == 0:
                return ""
            sub_str = s[0]

            def aroundCenter(in_s, left, right):
                """
                从给定的左右索引开始，向两侧扩展，直到不满足回文条件为止
                返回最长回文子串的起始和结束索引
                """
                len_s = len(in_s)
                while (left >= 0) and (right < len_s) and (in_s[left] == in_s[right]):
                    left = left - 1
                    right = right + 1
                return in_s[left + 1:right]

            for i in range(0, len(s)):
                # 以当前字符作为中心向两侧扩展
                sig1_str = aroundCenter(s, i, i)
                sig2_str = aroundCenter(s, i, i + 1)
                if len(sig1_str) > len(sig2_str):
                    sig_str = sig1_str
                else:
                    sig_str = sig2_str
                if len(sig_str) > len(sub_str):
                    sub_str = sig_str
            return sub_str

3、测试用例

    s=Solution()
    ts="babad"
    res=s.longestPalindrome(ts)
    print(res)