Shortest Palindrome

Problem: Shortest Palindrome

In this problem, we just try to see whether the sub-string is a palindrome and adjust length of sub-string to decide how to construct the shortest palindrome. We can only compare half of a string while judging palindrome so that we can reduce the running time.

Code in Python:

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

        return r+s