用python解决最长回文子串问题

Question

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

示例 1：

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

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

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

输入：s = "ac"
输出："a"

Answer 1

可以借助Manacher's Algorithm（马拉车算法）进行求解
这个算法是以每一个字符为中心, 向两边发散,同时,用一个数组p来记录以每一个字符为中心的回文串的一半的长度.
具体的可网上检索进行了解
代码如下：

class Solution:
    def longestPalindrome(self, s):
        def get_length(string, index):
            # 借助循环求出index为中心的最长回文字串
            start, length = index // 2, 0
           #获取字符串长度，并赋值非r_
            r_ = len(string)
            for i in range(1, index + 1):
                if index + i < r_ and string[index - i] == string[index + i]:
                    start = (index - i) // 2
                    length += 1
                else:
                    break
            return start, length

        s_list = [c for c in s]

        # 形成新串
        new_s = '#' + '#'.join(s_list) + '#'        

        #初始化赋值
        max_start = max_length = 0
        length = len(new_s)
        for index in range(0, length):
            start, r_length = get_length(new_s, index)
            if max_length < r_length:            #如果max_length小于r_length 则将start、r_length分别赋值给max_start、max_length
                max_start, max_length = start, r_length
        return s[max_start: max_start+max_length]