本文共 699 字，大约阅读时间需要 2 分钟。

最长回文子串,利用动态规划可以解出来,复杂度是O（n^2），空间复杂度是O（n）,因为我们可以用区间长度来进行动态规划,这样总是只需要3n的空间即可。base是size=1和0的情况,然后每次都增加1个长度,用长度为size-2的情况来分析。

class Solution(object):    def longestPalindrome(self, s):        n = len(s)        s+=' '        index= (0,0)        T = [[0]*(n+1) for i in range(3)]        for start in range(n):            T[0][start],T[1][start]=1,(s[start]==s[start+1])            if T[1][start]:index = (start,1)        for size in range(2,n):            for start in range(n-size):                T[(size%3)][start] = (s[start]==s[start+size] and T[(size-2)%3][start+1])                index = (start,size) if (T[size%3][start] and size>index[1]) else index        return s[index[0]:index[0]+index[1]+1]

转载地址：http://cmrkn.baihongyu.com/