leetcode with python:5. Longest Palindromic Substring

题目:

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)
那我们下题见