Longest Palindromic Substring

Question

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

Reference

results matching ""

    No results matching ""