Ежедневный вопрос по алгоритму — leetcode 5 — самая длинная подстрока палиндрома — python

алгоритм
Ежедневный вопрос по алгоритму — leetcode 5 — самая длинная подстрока палиндрома — python

【Название Описание】

[Метод 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]