【Название Описание】
[Метод 1: куриные идеи]
Двухслойная петля, квадратный уровень временной сложности. код выше
class Solution:
def longestPalindrome(self, s: str) -> str:
if (len(set(s))==1):return s
max1=0
re=''
for i in range(len(s)):
for j in range(1,len(s)-i):
zheng=s[i:i+j+1]
fan=zheng[::-1]
if(zheng==fan and max1<=len(zheng)):
max1=len(zheng)
re=zheng
if (len(re)==0):return s[0:1]
return re
Глядя на эффективность этого исполнения, это просто.
[Метод 2: динамическое программирование]Задача двумерного динамического программирования может использовать массив для хранения ij для формирования палиндрома, затем i от хвоста к началу, j от i+1 до хвоста, а затем, когда s[i]=s[j] равно нашли, посмотрите на эти два Является ли часть между ними палиндромом, если да, то обновите длину палиндрома, если нет, продолжайте. Таким образом, есть еще два слоя петель, и сложность возводится в квадрат.
class Solution:
def longestPalindrome(self, s: str) -> str:
right=left=0
dp=[]
for i in range(len(s)):
dp.append([False]*len(s))
dp[i][i]=True
i=len(s)-2
while(i>=0):
j=i+1
while(j<len(s)):
dp[i][j]=s[i]==s[j] and (dp[i+1][j-1] or j-i==1)
if(dp[i][j] and right-left<j-i):
right=j
left=i
j+=1
i-=1
return s[left:right+1]
Эффект все еще очень медленный:
[Способ 3: метод расширения центра]Слой циклов, один за другим, центрируется на элементах строки, а затем расширяется в обе стороны с помощью двойных указателей, чтобы найти самую длинную суб-палиндромную строку с центром на каждом элементе и сохранить самую длинную начальную позицию и длину. Эффективность немного улучшилась. Но временная сложность находится между O (n) и O (n * n), потому что каждый цикл также должен искать слева и справа.
class Solution:
def longestPalindrome(self, s: str) -> str:
if(len(s)<=1):return s
i=minstart=0
maxl=1
while i <len(s):
if(len(s)-i<maxl/2):
break
l=r=i
while(r<len(s)-1 and s[r]==s[r+1]):
r+=1
while(r<len(s)-1 and l>0 and s[l-1]==s[r+1]):
r,l=r+1,l-1
if(r-l+1>=maxl):
minstart,maxl=l,r-l+1
i+=1
return s[minstart:minstart+maxl]