https://leetcode.com/problems/shortest-palindrome/description/

shortest-palindrome.py

class Solution(object):
    

    def shortestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        def non_palindrome_index(s):
            i = 0
            while i < len(s) - i:
                if s[i] != s[-i-1]:
                    return i
                i += 1
            return -1
        if non_palindrome_index(s) == -1: return s
        
        i = 1
        while i < len(s):
            index = non_palindrome_index(s[:-i])
            # print i, s[:-i], index
            if index == -1:
                return s[-1:-i-1:-1] + s
            i += max(index-1, 1)