O(n) python solution with Manacher's Algorithm


  • 1
    S

    Spent some time understanding how this Manacher's algorithm works. This is a O(n) version with linear space consumption.

    We first transform the string 'aba' -> '#a#b#a#'

    The value in dp represents the longest step expand from the center i, so that the longest palindrome centered at i should be dp[i]-1.

    for each i, the center is the equivalent to max(dp[:i])

    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            s = '#' + '#'.join(s) + '#'
            dp = [1] * len(s)
            center = 0
            for i, _ in enumerate(s):
                if dp[center] + center > i:
                    dp[i] = min(dp[2*center-i], dp[center]+center-i) 
                while i - dp[i] >= 0 and i + dp[i] < len(s) and s[i-dp[i]] == s[i+dp[i]]:
                    dp[i] += 1
                if dp[i] > dp[center]:
                    center = i
            return s[center-dp[center]+2:center+dp[center]:2]
    

    I read the post from this link for the problem: http://articles.leetcode.com/longest-palindromic-substring-part-ii/. And this one is even better if you read Chinese: https://www.felix021.com/blog/read.php?2040


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.