Longest Palindromic Substring
Question
- leetcode: (5) Longest Palindromic Substring | LeetCode OJ
- lintcode: (200) 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,
and there exists one unique longest palindromic substring.
Example
Given the string = "abcdzdcab", return "cdzdc".
Challenge
O(n2) time is acceptable. Can you do it in O(n) time.
题解1 - 穷竭搜索
最简单的方案,穷举所有可能的子串,判断子串是否为回文,使用一变量记录最大回文长度,若新的回文超过之前的最大回文长度则更新标记变量并记录当前回文的起止索引,最后返回最长回文子串。
Python
class Solution:
# @param {string} s input string
# @return {string} the longest palindromic substring
def longestPalindrome(self, s):
if not s:
return ""
n = len(s)
longest, left, right = 0, 0, 0
for i in xrange(0, n):
for j in xrange(i + 1, n + 1):
substr = s[i:j]
if self.isPalindrome(substr) and len(substr) > longest:
longest = len(substr)
left, right = i, j
# construct longest substr
result = s[left:right]
return result
def isPalindrome(self, s):
if not s:
return False
# reverse compare
return s == s[::-1]
源码分析
使用left
, right
作为子串的起止索引,用于最后构造返回结果,避免中间构造字符串以减少开销。
复杂度分析
穷举所有的子串,$$O(C_n^2) = O(n^2)$$, 每次判断字符串是否为回文,复杂度为 $$O(n)$$, 故总的时间复杂度为 $$O(n^3)$$. 故大数据集下可能 TLE. 使用了substr
作为临时子串,空间复杂度为 $$O(n)$$.
题解2
class Solution:
# @return a string
def getlongestpalindrome(self, s, l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return s[l+1 : r]
def longestPalindrome(self, s):
palindrome = ''
for i in range(len(s)):
len1 = len(self.getlongestpalindrome(s, i, i))
if len1 > len(palindrome): palindrome = self.getlongestpalindrome(s, i, i)
len2 = len(self.getlongestpalindrome(s, i, i + 1))
if len2 > len(palindrome): palindrome = self.getlongestpalindrome(s, i, i + 1)
return palindrome
源码分析
假定扫描的每个字母是回文的中间位置(需要处理奇偶两种情况),从该位置向两头搜索寻找最大回文长度
复杂度分析
时间复杂度降到O(n^2)了
题解3
class Solution:
# @return a string
def longestPalindrome(self, s):
t = '$#' + '#'.join(s) + '#_'
p = [0] * 4010
mx, id, mmax, right = 0, 0, 0, 0
for i in range(1, len(t) - 1):
if mx > i:
p[i] = min(p[2 * id - i], mx - i)
else:
p[i] = 1
while t[i + p[i]] == t[i - p[i]]:
p[i] += 1
if i + p[i] > mx:
mx = i + p[i]
id = i
if mmax < p[i]:
mmax = p[i]
right = i
return s[right//2 - mmax//2: right//2 - mmax//2 + mmax - 1]
# debug
s = Solution()
print s.longestPalindrome('ASBAASBAAA')
另外还有一个O(n)的解法,具体参考下面的链接 http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html