LeetCode第五题：最长回文子串

5：

英文题面：

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。

示例 1：

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

示例 2：

输入: "cbbd"输出: "bb"

思路：

求回文子串，

最简单的思路是暴力搜索，检索所有的子串检查是不是回文串，这个时间复杂度为O(n^3)。

第二可以考虑中心扩展法，对字符串中每个字符考虑为回文串的中心，向两边扩张到最大，这里注意有两种回文串，一个是长度为奇数的回文串，中心为一个字符，长度为偶数的回文串，中心为2个相同的字符。这里时间复杂度是O(n^2)

第三：Manacher算法，时间复杂度为O(n)

实例给出第二种实现代码：

class Solution(object): def __init__(self): self.max_len = 0 self.start = -1 self.end = -1 def longestPalindrome(self, s): """ :type s: str :rtype: str """ for i in range(len(s)): self.find_str(i,i,s) self.find_str(i,i+1,s) return s[self.start:self.end+1] def find_str(self, left, right,s): while (left>=0 and right<len(s) and s[left] == s[right]): left -= 1 right += 1 if right - left - 1 > self.max_len: self.max_len = right - left - 1 self.start = left+1 self.end = right-1