Question: https://leetcode.com/problems/shortest-palindrome/
Question Name: Shortest Palindrome
This is a variant of Longest Palindromic Substring. The key point is to convert the original question as following:
1. Shortest Palindrome by adding any characters in the head. Therefore the original string “original” is going to be “***original”. Because the inserted characters could be ANY thing, we can guarantee that the added sub-string is a mirror of the tailing sub-string. So the question turns out to be:
2. Convert the original string to a palindrome by removing characters at the end of it. Furthermore, it’s equal to:
3. In the original string, what’s the longest Palindrome sub-string, which starts at the index 0.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | class Solution(object): def shortestPalindrome(self, s): """ :type s: str :rtype: str """ newS = "#"+"#".join(s)+"#" palHalfLenCenteringHere = [1] * len(newS) center, right = 0,1 for index in xrange(1, len(newS)): if index < right and index + palHalfLenCenteringHere[2*center-index] < right: # No way to extend the right. Thus the center is not changed. palHalfLenCenteringHere[index] = palHalfLenCenteringHere[2*center-index] else: # We MIGHT extend the right. And we DO change the center here. # IF we did NOT extend the right, the new center and old one have completely # the SAME effect on the next steps/rounds. center = index if index < right: # Use some pre-computed information palHalfLenCenteringHere[index] = right - center else: # Actually scanning from scratch palHalfLenCenteringHere[index] = 1 right += 1 # Try to extend the right while right < len(newS) and 2*center-right >= 0 and \ newS[right] == newS[2*center-right]: right += 1 palHalfLenCenteringHere[index] += 1 # Find the longest palindromic substring, which starts at the beginning. # We travel from the middle point to the begin point. Therefore the first # qualified sub-string is the longest one. for center in xrange(len(newS)//2, -1, -1): # Check whether this palindromic substring starts at index 0. if center - palHalfLenCenteringHere[center] + 1 == 0: halfLen = palHalfLenCenteringHere[center] result = newS[center + halfLen:][::-1] + newS return result.replace("#", "") # Should never be here. return None |
Just let you know that I have a pretty messy AC as well. A more elegant solution I peeked from discussion section is: reverse first and then compare substring, which requires an extra O(N) space and O(N^2) time complexity due to substring comparison. And fancier ones use KMP…
My version has no algorithm applied at all, simply “brute force” to cover all edge cases. Stupid but not simple ^_^, no extra space and pretty fast though…
Well, the algorithm is a bit complicate, and also elegant IMO. It works for most Palindrome related questions.