My recursive Python solution


  • 7

    The Idea is simple, we use j to compare character from end of s and beginning of s. If it's equal, increment j by 1.

    So we can use j-len(s) to divide s in two parts. The first part is that we don't know it's Palindrome. The second part its that we know for sure its the suffix of result and it may need reversed and insert at beginning of result.

    The fun part is this: s[::-1][:len(s)-j]
    if len(s)-j is 0, it will eliminate as '', otherwise it equals reversed(s[j-len(s):])
    It's same as:

    if len(s) - j == 0:
        return ''
    else:
        return s[j-len(s):][::-1]
    

    Whole solution:

        if not s or len(s) == 1:
            return s
        j = 0
        for i in reversed(range(len(s))):
            if s[i] == s[j]:
                j += 1
        return s[::-1][:len(s)-j] + self.shortestPalindrome(s[:j-len(s)]) + s[j-len(s):]

Log in to reply
 

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