題目:

Given a string s, return the longest palindromic substring in s.

給定一個字串,找出其中最長對稱子字串

這題我的解法偏暴力解

class Solution:
    def longestPalindrome(self, s: str) -> str:
        record1=[]
        record2=[]
        
        for i in range(len(s)): #紀錄最小奇數型對稱字串
            record1.append(i)

        for i in range(len(s)-1): #紀錄最小偶數型對稱字串
            if s[i]==s[i+1]:
                record2.append(i)
                
        i1=1
        i2=2
        while True:
            temp=[]
            i1=i1+2
            for i in record1:
                if i-1>=0 and i+i1-2<len(s) and s[i-1]==s[i+i1-2]:
                    temp.append(i-1)
            if temp==[]:
                i1=i1-2
                break
            else:
                record1=temp
                
        while True:
            temp=[]
            i2=i2+2
            for i in record2:
                if i-1>=0 and i+i2-2<len(s) and s[i-1]==s[i+i2-2]:
                    temp.append(i-1)
            if temp==[]:
                i2=i2-2
                break
            else:
                record2=temp
                
        if record2==[]: #防止連最小偶數型對稱字串都沒有
            return s[record1[0]:record1[0]+i1]
        else:
            if i1>i2:
                return s[record1[0]:record1[0]+i1]
            else:
                return s[record2[0]:record2[0]+i2]

對稱字串有分奇數型跟偶數型,如aba及abba
我分兩種可能去找

用兩個項目來記錄:紀錄對稱字串頭index的record,跟紀錄對稱字串長度的i
每次都比較record內字串兩側是否相等,若相等就放入record,否則排除
接著i+2進入下一次擴張
一旦發現這次擴張導致record變為空陣列
即表示上一次擴張紀錄的字串為此型態最長的對稱字串
record復原為上一次擴張的樣貌,i也-2

最後比較兩種型態的最長字串何者較長
回傳該型態record中的其中一筆字串即可
最後執行時間1632ms(faster than 46.04%)

講了老半天結果是個快超時的解XD

討論區有另一種想法的解
看起來簡潔了些

class Solution:
    def longestPalindrome(self, s: str) -> str:        
        lenres=0
        res=""
                       
        for i in range(len(s)):
            l=i
            r=i
            while l>=0 and r<len(s) and s[r]==s[l]:
                if (r-l+1)>lenres:
                    lenres=r-l+1
                    res=s[l:r+1]
                l=l-1
                r=r+1
            
        for i in range(len(s)):
            l=i
            r=i+1
            while l>=0 and r<len(s) and s[r]==s[l]:
                if (r-l+1)>lenres:
                    lenres=r-l+1
                    res=s[l:r+1]
                l=l-1
                r=r+1
                
        return res

考慮奇偶兩種可能對每個字元下去做擴張
若有發現更長的字串就覆蓋原先紀錄的值
最後回傳紀錄值
最後執行時間1114ms(faster than 75.24%)

快了些,但還不夠快
接下來就是今天的主角,Manacher's Algorithm(馬拉車演算法)
專門用來找一個字串裡的最長回文的演算法(一直打最長對稱子字串好累,改稱回文)
直接用這題來講解它的實作方法應該會比較清楚

class Solution:
    def longestPalindrome(self, s: str) -> str:
        newstr=""
        for i in s:
            newstr=newstr+"*"+i
        newstr="$"+newstr+"*%"
        
        record=[0]*len(newstr)
        
        center=0
        right=0
        for i in range(1,len(newstr)-1):
            mirror=2*center-i
            
            if i < right:
                record[i]=min(right-i,record[mirror])
                
            while newstr[i+record[i]+1]==newstr[i-record[i]-1]:
                record[i]=record[i]+1
                
            if i+record[i]>right:
                center=i
                right=i+record[i]
                
        anslen=max(record)
        ansindex =record.index(anslen)
        return newstr[ansindex-anslen:ansindex+anslen].replace('*', '')

首先先對字串做特殊處理,在每個字元兩側都放有" * "
這樣我們就能一次顧慮到兩種型態的回文下去做擴張
接著在處理後字串兩側放入奇異且相異的兩個符號("$","%")
這樣我們就不用顧慮到字串邊際(這兩個符號會擋下來)

我們有個陣列record紀錄以每個字元到以其為中心的最長回文右邊界的距離
中心(center)和右邊界(right)都先設0,之後會用到
對稱點(mirror)是指當前位置以center為中心的對稱點

這邊講一個重要的性質,以字串a(b)a{c}a[b]ac為例(無視括號,只是做記號)
我們知道以(b)為中心的最長回文長度是3
而以{c}為中心的最長回文長度是7
透過上行給出的信息,我們可以知道[b]為中心的最長回文長度至少>3
為什麼?因為我們知道{c}的左右兩邊的三個字元長得一模一樣
雖然我們知道[b]為中心的最長回文長度是5
但我們至少能從長度3開始擴張

馬拉車演算法就是利用這個性質來提升整個程式的效率
所以上述的center和right就是用來記錄
如上面{c}中心回文這樣能成為幫忙推算最長回文的存在

理論講完終於可以進入過程了
當一個字元發現自己身在以center為中心的最長回文(以下稱c回文)範圍中
我們便可以從record繼承當初在其對稱點已經紀錄的數據開始擴張
但要記得繼承的數據不能超出c回文的右邊界
因為再外就是盲區,是不確定的

而當擴張完發現該字元最長回文的右邊界超過c回文的右邊界
它就會變成我們的新center,其右邊界也會成為新的right
畢竟我們一定是想拿能預測更多字元最大回文長度,涵蓋範圍更多的回文當我們的c回文

結束後只要透過record找出最長回文
去掉" * "後回傳即可

最後執行時間188ms(faster than 97.48%)

本題學習到的重點:馬拉車演算法(Manacher's Algorithm)
那我們下題見