Shortest Palindrome

这种等级的题基本想出来一道要人半条命，微笑呵呵...

思路上来说首先就是一定要发现在只允许往前加字符串来构成对称字符串的前提下，有两点是很明确的

• 这个最短对称字符串长度不可能超过2n，设想输入字符串是一个没有任何对称的字符串（类似abcdefg），这样很明显能看出来就是反过来加到左边即是最短字符串了
• 另外一点就是这个最短串必然是去除掉包含首字母的最长对称子串后的剩下的那部分反过来加到左边构成的，原因也很简单，设想左边起始的字符并不在这个对称子串中，则相当于当前对称结构左右两边必有一处是不相等字符构成的，那样的话无论如何都无法构成对称字符串了

明确了上述两点，其实题目就很清晰了，首先用马拉车构建一个关于输入字符串以当前位置为中心构建的对称串的半径数组，然后在这个数组中找一个离起点最远，但是它的对称串又包含了起点的位置，也就是起点就是它最外围的一个对称点，然后把这个字符提取出来，因为马拉车处理的半径数组是包含了井号的数组，我们只需要字符部分，这个子字符串拿到后，将剩下的部分反过来加到左边即可，下面是代码

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

        '''下面部分都是马拉车'''

        length = len(s)
        string = '#' + '#'.join(s) + '#'
        n = len(string)
        p = [0] * n
        maxBorder, maxCenter = 0, 0
        res = [0, 0]
        for i in range(n):
            if maxBorder > i:
                p[i] = min(p[2 * maxCenter - i], maxBorder - i)
            else:
                p[i] = 1
            while i - p[i] >= 0 and i + p[i] < n and string[i - p[i]] == string[i + p[i]]:
                p[i] += 1
            if maxBorder < p[i] + i:
                maxBorder = p[i] + i
                maxCenter = i
                if p[i] > res[1] - res[0]:
                    res = [maxCenter, maxBorder]

        '''下面是找到那个最长对称子串'''

        index = 0
        for i in xrange(length, -1, -1):
            if i + 1 - p[i] <= 0:
                index = i
                break

        '''剩下部分取反加到左边'''    

        tmp = [x for x in string[ : index + p[index]] if x != '#']
        left = s[len(tmp) : ][::-1]
        return left + s

上面的缩写版

class Solution(object):
    def shortestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        string = '#' + '#'.join(s) + '#'
        maxCenter, maxBorder = 0, 0
        n = len(string)
        res = [0, 0]
        p = [0] * n

        for i in xrange(n):
            if maxBorder > i:
                p[i] = min(p[2 * maxCenter - i], maxBorder - i)
            else:
                p[i] = 1
            while i + p[i] < n and i - p[i] >= 0 and string[i + p[i]] == string[i - p[i]]:
                p[i] += 1
            if i + p[i] > maxBorder:
                maxCenter, maxBorder = i, i + p[i]
                if p[i] > res[1] - res[0]:
                    res = [maxCenter, maxBorder]

        index = 0
        for i in xrange(n):
            if i - p[i] <= 0:
                index = i

        return ''.join([x for x in string[index + p[index] : ][::-1] + string if x != '#'])

上面的马拉车版本是O(n)时间复杂度的一种解法，还有一种O(n^2)的暴力解，即强行比对包括首字符的最长对称字串，再把剩下的部分反转拼出来就是了

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

        return s[index + 1:][::-1] + s

因为这里暴力解可以，那也说明解最长对称子串的DP解法也可以在这里用，主要就是用的那个dp矩阵，另外O(n^2) 的解法还有一种双指针递归搜索的方法，O(n)的做法则还可以运用KMP算法的表，以后有时间再研究这些吧...

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