Shortest Palindrome https://leetcode.com/problems/shortest-palindrome/
- X = "abcd". If we reverse X and add it to front of X, we will for sure have a palindrome."dcbaabcd".
- However there may be redundant characters in this palindrome which doesnt make it the shortest. For example: "dcbabcd" is a valid palindrome with one less character. Try other examples: s="ananab". rev_s = "banana". New Palindrom: "bananaananab". Shorter one: "banananab"
- The general approach is then: X = PS. P is the longest prefix which is also a palindrome. S is remainder suffix. Thus the new palindrome is: New palindrom = SPS. Implementing above in a naive manner gives you an N^2 algorithm.
- Notice one more thing: X = "ananab" and R_X = "banana". Longest prefix in X which is a suffix in R_X is "anana". Remove that from R_X and we have "ban" + "ananab" as palindrome.
- KMP can be used to solve *Longest prefix in X which is a suffix in RX *
- Another interesting idea is to use startswith API in Python. s.startswith(rev_s[i:]) and we vary i from 0 to N. This automatically gives us the longest prefix to work with.
class Solution(object): def shortestPalindrome(self, s): """ :type s: str :rtype: str """ if s == "": return s rev_s = s[::-1] for i in range(len(s)): if s.startswith(rev_s[i:]): return rev_s[:i]+s