Python solution with detailed explanation


  • 1
    G

    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
    

Log in to reply
 

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