最短回文串

题目链接

题目原文 给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1:
输入: "aacecaaa"
输出: "aaacecaaa"
示例 2:
输入: "abcd"
输出: "dcbabcd"

题目分析

最简单的思路是求出所给串中的最长回文串,例如:给定串abcdcbaaaa,其中的最长回文串为abcdcba,找出该串的位置后,只需在所给串前加上后续子串。因此,题目可化简为求所给串的最长回文串的位置。

解题方法:

暴力法

首先,按照上面的思路,我想到的就是遍历子串并判断是否是回文串,并返回回文串的位置。判断是否是回文串的方法极其简单,只需将所给字符串翻转,并与原字符串判断是否相等。如下所示:

def isPalindrome(self,string:str)->bool:
         return string == ''.join(list(reversed(string)))

之后,我遍历所给串的子串,直到找到最长回文子串,若找不到直接将原串复制并翻转合并。代码如下:

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        if len(s)==0 or len(s)==1:
            return s 
        #寻找回文串的中点
        #找出最长的回文子串
        max_length=1
        for i in reversed(range(2,len(s)+1)):
            #判断s[:i]是否是回文子串
            if self.isPalindrome(s[:i]):
                max_length=i
                break
        # print(max_length)
        return s[max_length:][::-1]+s
    def isPalindrome(self,string:str)->bool:
         return string == ''.join(list(reversed(string)))

但是,这种方法的时间复杂度为O(n2)O(n^2),在面对极端串的时候,时间极长,例如:aabbbbbbbbbbbbbb....

Manacher算法

俗称"马拉车"算法,该算法将查询最长回文子串的时间的时间复杂度降低到了O(n)O(n),下面开始介绍算法过程。

字符串预处理

我们知道回文串可分为偶回文(abba)和奇回文(abcba),在处理奇偶的问题上会比较繁琐,因此,算法使用了一个技巧,做法如下:

  1. 在字符串首尾及每个字符都插入一个'#',这样可以使得原先子串内的奇偶回文都变成奇回文;
  2. 再在首尾插入'$','^',这样在中心扩展回文的时候就不需要判断数组越界;
  3. 上述插入的定位符,不能出现在原字符串中。

举个例子: s="aacecaaa",转换为trans_string="$#a#a#c#e#c#a#a#a#^",观察到原本子串中的偶回文"aa"转为奇回文"#a#a#"。

计算辅助数组

该辅助数组ppp[i]p[i]表示以i为中心的最长回文串的半径,例如:

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
t $ # a # a # c # e # c # a # a # a # ^
p 0 1 2 3 2 1 2 1 8 1 2 1 2 3 4 3 2 1 0

不难发现,p[i]中的最大值减1,即为所给串的最长回文子串。那么如何计算辅助数组呢?

这里再引入两个概念,max_right当前发现的回文子串的右边界,该值取最大值,以及pos表示max_right对应的回文子串的对称轴位置。因此,这两个值在遍历过程中是及时更新的。

给定这两个值之后,就可以方便地更新辅助数组p了,
假定现在已经计算出pos和max_right的值,我们讨论p[i]的值如何由已知回文串的信息来确定,为了便于讨论,再引入j=2*pos-i,即i关于pos的对称点,示意图如下:

各关键的位置各关键的位置

那么根据回文串的性质,如果i在max_right内,i是以pos为中心的回文串的一部分,那么i的回文串长度可以直接参考j的回文串长度,同时i的回文串长度一定不会超过max_right-i,因为这样的话就违背了max_right是最远边界的假设。
所以,我们可以得到下式:

if i<max_right:
  p[i]=min(p[2*pos-i],max_right-i)

对于max_right和pos的更新,以及p[i]的进一步扩展,可以参考下面代码,有详细的注释:

def manacher(self,s):
        trans_string = self.transformString(s)
        # 计算辅助数组
        # p[i]表示以i为中心的最长回文的半径
        p=[0]*len(trans_string)
        # 初始化 pos和边界max_right
        # 表示当前访问到的所有回文子串,所能触及到的最右的字符位置,此外pos表示max_right对应的回文串的对称轴所在的位置
        pos=max_right=0
        for i in range(1, len(trans_string)-1):
            if i < max_right:
                p[i]=min(p[2*pos-i],max_right-i)
            else:
                p[i]=1
            #尝试扩展最长回文子串,无需判断边界,因为两端添加了$,^
            while trans_string[i-p[i]]==trans_string[i+p[i]]:
                p[i]+=1 
            #更新max_right,因为max_right表示当前最长回文串的右边界
            if max_right<i+p[i]:
                pos=i
                max_right=i+p[i]
        return p

解决当前问题

manacher的初始解决问题是,快速查找所给串的最长回文子串,但与所给题目不同,所给题目是要求判断从字符串开头到某一结尾是否是回文子串。因此,在获得p之后,我们可以基于p加速判断某一个串是否是回文串。具体如下:

def isPalindrome(self, L, R, p) :
        L = L*2 + 2 #将L映射到p数组的索引
        R = R*2 + 2 
        mid = int((L+R)/2) #计算L和R的对称点
        if 0 <= mid and mid < len(p) and R-L+1 <= p[mid]*2 :
            return True;
        return False;

于是我们仍可以使用上述蛮力法的框架,给出解决方案:

下述代码可直接运行到leetcode,如有不清楚的地方,欢迎沟通讨论。

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        if len(s)==0 or len(s)==1:
            return s 
        p=self.manacher(s)
        #寻找回文串的中点
        #找出最长的回文子串
        max_length=1
        print(p)
        for i in reversed(range(0,len(s))):
            #判断s[:i]是否是回文子串
            print(i)
            if self.isPalindrome(0,i,p):
                max_length=i+1
                break
        print(max_length,s[max_length:])
        return s[max_length:][::-1]+s
        
       
    def manacher(self,s):
        trans_string = self.transformString(s)
        # 计算辅助数组
        # p[i]表示以i为中心的最长回文的半径
        p=[0]*len(trans_string)
        # 初始化 pos和边界max_right
        # 表示当前访问到的所有回文子串,所能触及到的最右的字符位置,此外pos表示max_right对应的回文串的对称轴所在的位置
        pos=max_right=0
        for i in range(1, len(trans_string)-1):
            if i < max_right:
                p[i]=min(p[2*pos-i],max_right-i)
            else:
                p[i]=1
            #尝试扩展最长回文子串,无需判断边界,因为两端添加了$,^
            while trans_string[i-p[i]]==trans_string[i+p[i]]:
                p[i]+=1 
            #更新max_right,因为max_right表示当前最长回文串的右边界
            if max_right<i+p[i]:
                pos=i
                max_right=i+p[i]
        return p

    # 将初始串abcd转换为$#a#b#c#d#^
    def transformString(self,s:str) -> str:
        return '$#'+'#'.join(list(s))+'#^'
    
    def isPalindrome(self, L, R, p) :
        L = L*2 + 2
        R = R*2 + 2
        mid = int((L+R)/2)
        if 0 <= mid and mid < len(p) and R-L+1 <= p[mid]*2 :
            return True;
        return False;

偷鸡方法

看题解时,还看到一个有趣的方法,在python中可以快速实现。
我们从另一个方向思考问题,给定串"aacecaaa",由回文串的性质,将串翻转后,仍等于原字符串,因此我们先翻转"aacecaaa"得到"aaacecaa",而我们期望的结果是"aaacecaaa",很显然,我们需要找到"aacecaaa"和"aaacecaa"重复的部分"aacecaa",并将两串拼接。
python中有一个非常方便的函数,startswitch,该方法用于检查字符串是否是以指定子字符串开头,如果是则返回 True,否则返回 False。如果参数 beg 和 end 指定值,则在指定范围内检查。

str.startswith(str, beg=0,end=len(string));

代码如下:

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        reverse = s[::-1]
        for i in range(len(s) + 1):
            if s.startswith(reverse[i:]): #仍是从左往右遍历是否有回文串,但是由于内置函数的关系,性能很好
                return reverse[:i] + s

参考

Manacher算法
leetcode:jam 思路简单,性能高效达到100
startswitch 方法