Short Python codes, Discuss on 2 Methods, both O(n) time


  • 2

    Our goal is to find the longest palindrome starting from the first index.

    1st method:
    Concatenate the input string with its reverse by a special character, i.e. '$'. Then we find the longest palindrome from the first index by finding the prefix suffix (see kmp algorithm) at the last index.

    def LPS(p):
        lps = [0] * len(p)
        l = 0
        for i in range(1, len(p)):
            while l > 0 and p[i] != p[l]:
                l = lps[l-1]
            if p[i] == p[l]:
                l += 1
                lps[i] = l
        return lps
    
    def shortestPalindrome(s):
        lps = LPS(s+'$'+s[::-1])
        return s[lps[len(lps)-1]:len(s)][::-1] + s
    

    But this method will not work if our input string also contains that special character. Another method to get around this is to use KMP matching. Consider i going from first index to the right as the index for the pattern, and j goes from the last index to the left as the index in the string to match in KMP.

    def LPS(p):
        lps = [0] * len(p)
        l = 0
        for i in range(1, len(p)):
            while l > 0 and p[i] != p[l]:
                l = lps[l-1]
            if p[i] == p[l]:
                l += 1
                lps[i] = l
        return lps
    
    def shortestPalindrome(s):
        lps = LPS(s)
        i = 0; j = len(s)-1
        while i < j:
            while i > 0 and s[i] != s[j]:
    	        i = lps[i-1]
    	    if s[i] == s[j]:
                i += 1
    	    j -= 1
        return s[(i+j)+1:len(s)][::-1] + s

Log in to reply
 

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