【LeeCode 中等 字符串】5 最长回文子串

想要看更加舒服的排版、更加准时的推送
关注公众号“不太灵光的程序员”
每日八点有干货推送，微信随时解答你的疑问

5 最长回文子串 python3

中等 字符串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例 2：

输入: “cbbd”
输出: “bb”

分析过程
回文串 就是 正序和逆序是一个结果的字符串叫回文串
最长回文子串 是找出 在字符串中 正序和逆序是一个结果的子串

# 86%
# 执行用时：812 ms
# 内存消耗：13.7 MB
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2: return s

        max_len = 0
        start_index = 0

        def hw_len(left, right):
            while left >= 0 and right < n and s[left] == s[right]:
                left -= 1
                right += 1
            return right - left - 1, left + 1

        # 中心扩散法
        for i in range(n-1):
            # 单核心
            len1, start_index1 = hw_len(i, i)
            # 双核心
            len2, start_index2 = hw_len(i, i+1)

            if len1 > max_len:
                max_len = len1
                start_index = start_index1
            if len2 > max_len:
                max_len = len2
                start_index = start_index2

        return s[start_index: start_index+max_len]


s = Solution()
st = "cbbd"
ret = s.longestPalindrome(st)
print(ret, 'bb')
st = "babad"
ret = s.longestPalindrome(st)
print(ret, 'bab')
st = "abcda"
ret = s.longestPalindrome(st)
print(ret, "a")
st = "ac"
ret = s.longestPalindrome(st)
print(ret, 'a')
st = "bb"
ret = s.longestPalindrome(st)
print(ret, 'bb')
st = ""
ret = s.longestPalindrome(st)
print(ret)
st = "aacedaa"
ret = s.longestPalindrome(st)
print(ret, "aa")
st = "aacdefcaa"
ret = s.longestPalindrome(st)
print(ret, "aa")
st = "saacdefcaa"
ret = s.longestPalindrome(st)
print(ret, "aa")
st = "abcdbbfcba"
ret = s.longestPalindrome(st)
print(ret, "bb")
st = "onoranynartionso"
ret = s.longestPalindrome(st)
print(ret, "ranynar")