Shortest Palindrome

题目描述

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

解题方法

这一道题可以借鉴longest palindrome substring的方法，从每个pivot搜palindrome, 如果左边能够停留在开头，说明可以通过在开头加characters找到shortest palindrome.

注意

• 这里其实只需要找一半, 因为结果的左半部分不完整，必然是在前半部分有一个pivot
• 从后往前扫，这样找到了结果就可以返回了

KMP解法

O(n)的算法，需要理解一下 理解kmp kmp geeksfor geeks shortest Palindrome

Solution

利用longest palindrome substring

python超时

class Solution(object):
    def shortestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return ""

        length = len(s)
        minLength = sys.maxint
        result = ""
        if self.isPalindrome(s):
            return s


        if length % 2 == 1:
            half = length / 2 + 1
        else:
            half = length / 2

        for i in range(1, half):
            # pivot is between i-1, i
            low = i - 1
            high = i
            while low >= 0 and high < length and s[low] == s[high]:
                low -= 1
                high += 1
            if low == -1:
                pLength = (high - 1) - (low + 1) - 1
                doubleLength = (length - 1) - high + 1
                if minLength > pLength + 2 * doubleLength:
                    minLength = pLength + 2 * doubleLength
                    result = s[length-1:high-1:-1] + s

            # pivot is i
            low = i - 1
            high = i + 1
            while low >= 0 and high < length and s[low] == s[high]:
                low -= 1
                high += 1
            if low == -1:
                pLength = (high - 1) - (low + 1) - 1
                doubleLength = (length - 1) - high + 1
                if minLength > pLength + 2 * doubleLength:
                    minLength = pLength + 2 * doubleLength
                    result = s[length-1:high-1:-1] + s
        return result

    def isPalindrome(self, s):
        length = len(s)
        if length == 0 or length == 1:
            return True

        left, right = 0, length - 1
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                return False
        return True

class Solution(object):
    def shortestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return ""

        length = len(s)
        minLength = sys.maxint
        result = ""
        if self.isPalindrome(s):
            return s

        for i in range(length / 2, -1, -1):
            # pivot is between i-1, i
            if s[i] == s[i-1]:
                result = self.scanFromCenter(s, i-1, i)
                if result:
                    return result
            else:
                result = self.scanFromCenter(s, i, i)
                if result:
                    return result

    def scanFromCenter(self, s, l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1

        if l >= 0:
            return None

        result = s[len(s)-1:r-1:-1] + s


    def isPalindrome(self, s):
        length = len(s)
        if length == 0 or length == 1:
            return True

        left, right = 0, length - 1
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                return False
        return True

Reference