【中心扩散法manacher】5--最长回文子串

也是牛客网 NC17 题
参考：https://www.cxyxiaowu.com/2869.html

马拉车解法

# -*- coding:utf-8 -*-

class Solution:
    def getLongestPalindrome(self, A, n):
        # write code here
        newStr = '#'
        for i in range(len(A)):
            newStr += A[i]
            newStr += '#'
        
        note = []
        for index in range(len(newStr)):
            left = index - 1
            right = index + 1
            size = 0
            while left >= 0 and right < len(newStr):
                if newStr[left] == newStr[right]:
                    size += 1
                else:
                    break
                
                left -= 1
                right += 1
            note.append(size)
        
        return max(note)

如果还要输出最长的回文子串以及长度，格式是 ["aba", "3"]

# -*- coding:utf-8 -*-

class Solution:
    def getLongestPalindrome(self, A, n):
        # write code here
        newStr = '#'
        for i in range(len(A)):
            newStr += A[i]
            newStr += '#'

        note = []
        mapSubstr = {}
        for index in range(len(newStr)):
            left = index - 1
            right = index + 1
            size = 0
            while left >= 0 and right < len(newStr):
                if newStr[left] == newStr[right]:
                    size += 1
                else:
                    note.append(size)
                    mapSubstr[size] = newStr[left+1:right].replace('#', '')
                    break

                left -= 1
                right += 1
            note.append(size)
            mapSubstr[size] = newStr[left + 1:right].replace('#', '')
        return [mapSubstr[max(note)], str(max(note))]

动态规划

留坑！