Longest Palindromic Substring
英文原文
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
中文原文
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000
Manacher算法
"马拉车"算法可在0(N)时间复杂度下实现最长回文数的搜寻
回文半径数组radius
回文半径数组radius是用来记录以每个位置的字符为回文中心求出的回文半径长度，如下图所示，对于p1所指的位置radius[6]的回文半径5，每个位置的回文半径组成的数组就是回文数组，所以#a#c#b#b#c#b#d#s#的回文半径数组为[1, 2, 1, 2, 1, 2, 5, 2, 1, 4, 1, 2, 1, 2, 1, 2, 1]
image.png
最右回文右边界R
一个位置最右回文右边界指的是这个位置及之前的位置的回文子串，所到达的最右边的地方。比如对于字符串#a#c#b#b#c#b#d#s#，求它的每个位置的过程如下：
image.png
动态规划题解
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# 使用动态规划，用空间换时间，把问题拆分
str_length = len(s)
max_length = 0
start = 0
for i in range(str_length):
if i - max_length >= 1 and s[i-max_length-1: i+1] == s[i-max_length-1: i+1][::-1]:
start = i - max_length - 1
max_length += 2
continue
if i - max_length >= 0 and s[i-max_length: i+1] == s[i-max_length: i+1][::-1]:
start = i - max_length
max_length += 1
return s[start: start + max_length]
