Elegant '#' insertion technique, O(n) python code


  • 0
    Y
    class Solution(object):
        def shortestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            if not s:
                return ""
            s = "#" + "#".join(s) + "#"
            dp = [0] * len(s)
            center = 0
            max_idx = 0
            for i in xrange(len(s)//2 + 1):
                if dp[center] + center >= i:
                    dp[i] = min(dp[2*center -i], dp[center] + center - i)
                while i - dp[i] > 0 and s[i-dp[i]] == s[i+dp[i]]:
                    dp[i] += 1
                if i - dp[i] == 0:
                    max_idx = i
                if dp[i] +i > dp[center] + center:
                    center = i
            
            s = s[max_idx + dp[max_idx] + 1:][::-1] + s
            return s.replace('#', '')
    
    

    This is inspired by the '#' insertion idea for shortest palindrome problem.
    O(n) time and easy to understand, if you know this technique for that problem


Log in to reply
 

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