Longest Palindromic Substring

非常经典的一道字符串处理题，这道题有多种解法可以求得答案，时间复杂度也不尽相同，包括区间DP矩阵递推，记忆化搜索DP，字符串对称暴力比对以及马拉车，下面具体解释各种方法

马拉车，重要性不用多说了，上面那道题就是基于它的p数组才能做的，原理太复杂了，也没必要搞得太懂，只需要记住p[i]代表以i为中心的对称子字符串的半径是多少，下面是代码，没得选，死背而已

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

        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]

        return ''.join([x for x in string[2 * res[0] - res[1] + 1 : res[1]] if x != '#'])

O(n^2)的区间DP矩阵递推算法，这道题其实如果用DP的思想来看，不难看出一个状态转移方程

dp[i][j] = dp[i + 1][j - 1] & string[i] == string[j]

意思其实就是字符串区间[i,j]这段字符是否对称取决于string[i]==string[j]还有抛开左右边界字符的这段字符串是否为对称串，如果这样看就很容易发现这就是一个区间类动态规划了，即要求的最终结果不在dp[n][m]而在dp[0][m]或者dp[n][0]（这是区间类DP最明显的特征），当然最容易想到的方法还是记忆化搜索了，但是此题记忆化搜索会TLE所以暂且不表，我们用矩阵递推的方式来重新实现记忆化搜索的过程，不难想到，dp[i][i]对任意i来说都为真，因为单个字符串永远对称，所以我们可以从对角线作为起始点由短字符串往更长的字符串去递推，在将字符串内任意区间是否为对称串的结果都找出来后，我们就可以通过比较区间长度来找最长的对称子串了，下面是代码

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        dp = [[False] * n for _ in xrange(n)]
        for i in xrange(n):
            dp[i][i] = True

        start, end = 0, 0
        res = -sys.maxint
        for i in xrange(n):
            for j in xrange(i - 1, -1, -1):
                # 如果i，j是相邻的，我们只用对比两个字符串是否相等就可
                dp[j][i] = (dp[j + 1][i - 1] & (s[j] == s[i])) if i - j > 1 else s[j] == s[i]
                if dp[j][i] and i - j + 1 > res:                # 这里是在找最长对称子字符串的起始位置
                    res = i - j + 1
                    start, end = j, i

        return s[start : end + 1]

第三种方法就是暴力的字符串扩展比对了，这里使用了一种扩展方法来使得奇数对或者偶数对都可以通过同一个算法来求得长度，一些小的boundary case非常需要注意，本身算法倒是没有什么难理解的

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        length = 0
        start, end = 0, 0
        for i in xrange(n):
            odd = self.expand(s, i, i, n)
            even = self.expand(s, i, i + 1, n)
            cur_long = max(odd, even)
            if cur_long > length:
                length = cur_long
                start = i - (length - 1) / 2                # 这里注意对奇偶长度不同的字符串的统一处理
                end = i + length / 2                        

        return s[start : end + 1]

    def expand(self, string, start, end, n):
        while start >= 0 and end < n:
            if string[start] == string[end]:
                start -= 1
                end += 1
            else:
                break
        return end - start - 1                              # 最外边两个字符是不符合条件的，所以是减一不是加一