Python solution with detailed explanation

• Solution

Shortest Palindrome https://leetcode.com/problems/shortest-palindrome/

1. X = "abcd". If we reverse X and add it to front of X, we will for sure have a palindrome."dcbaabcd".
2. 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"
3. 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.
4. 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.
5. KMP can be used to solve *Longest prefix in X which is a suffix in RX *
6. 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.
https://discuss.leetcode.com/topic/14542/ac-in-288-ms-simple-brute-force
``````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
``````

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