My Python Solution

  • 2

    I don't think this is most efficient. This algorithm compares: n/2 letters, (n-1)/2 letters, (n-2)/2 letters... 1 letter. So the worst case complexity is n^2.

    class Solution(object):
        def shortestPalindrome(self, str):
            :type str: str
            :rtype: str
            l = len(str)
            revstr = str[::-1]
            for i in xrange(l):
                if str[:(l-i+1)/2] == revstr[i:(l+i+1)/2]:
                    return  revstr[:i] + str
            return  revstr[:-1] + str

Log in to reply

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