Solution to Shortest Palindrome by LeetCode

8 Jun


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.

2 Replies to “Solution to Shortest Palindrome by LeetCode

  1. 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…

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!