Python O(N) solution...Manacher's Algo


  • 0
    M

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        #Manacher Algo O(n)
        n = len(s)
        center = right = 0
    
        T = self.preprocess(s)
        # Below list track length of pallindrome at each center
        P = [0]*len(T)
    
    
        for i in xrange(1, len(T) - 1):
            i_mirror = 2 * center - i
            if i < right:
                P[i] = min(right - i, P[i_mirror])
            else:
                P[i] = 0
            while T[i+1+P[i]] == T[i-1-P[i]]:
                P[i] += 1
    
            if i + P[i] > right:
                center, right = i, i + P[i]
    
        max_i = 0
        for i in xrange(1, len(T) - 1):
            if P[i] > P[max_i]:
                max_i = i
    
        start = (max_i - 1 - P[max_i]) // 2
    
        return s[start : start + P[max_i]]
    
    def preprocess(self, s):
         if not s:
            return ['^','$']
         T = ['^']
         for c in s:
             T += ['#',c]
         T += ['#','$']
         return T

Log in to reply
 

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