By

文章目录
  1. 1. 动态规划
  2. 2. manacher

求最长回文子串的一道题，开始用动态规划做，超时，然后hard告诉我有manacher方法，两种方法的代码都实现了下，放在下面用于记忆。

动态规划

复杂度o(n*n)，temp[i][j]表示s中从第i到j个字符串是否为回文串，如果是取0，否则取1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def longestPalindrome(s):
    if(len(s)<=1):
        return s
    temp = [([0] * len(s)) for i in range(len(s))]
    longstr = s[0]
    for i in range(0,len(s)):
        temp[i][i]=1
    for i in range(0,len(s)-1):
        if(s[i] == s[i+1]):
            temp[i][i+1] = 1
            longstr = s[i:i+2]
    for length in range(3,len(s)+1):
        for i in range(0,len(s)-length+1):
            j = i+length-1
            if(s[i]==s[j]and temp[i+1][j-1]):
                temp[i][j] = temp[i+1][j-1]
                if(length>len(longstr)):
                    longstr = s[i:j+1]
            else:
                temp[i][j] = 0
    return longstr

manacher

复杂度o(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
   def longestPalindrome(self, s):
       s = '^'+'#'+'#'.join(s)+'#'+'$'
       maxlen = 0
       maxright = 0
       longstr = ""
       zhongxinpoint = 0
       r = [0]*len(s)
       for i in range(2,len(s)):
           temp = i
           j = 1
           if(i<maxright):
               j = min(r[2*zhongxinpoint-i],maxright-i)
           while(temp-j>-1 and temp+j <len(s) and s[temp-j] == s[temp+j]):
               j = j+1
           r[i] = j
           if(i+j-1>maxright):
               maxright = i+j-1
               zhongxinpoint = i
           if(j*2-1>maxlen):
               maxlen = j*2-1
               longstr = "".join(s[i-j+1:i+j].split("#"))
       return longstr

文章目录
  1. 1. 动态规划
  2. 2. manacher