目录

0214:最短回文串(★★)

力扣第 214 题

题目

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

示例 1:

输入:s = "aacecaaa"
输出:"aaacecaaa"

示例 2:

输入:s = "abcd"
输出:"dcbabcd"

提示:

  • 0 <= s.length <= 5 * 104
  • s 仅由小写英文字母组成

相似问题:

分析

  • 问题等价于找到 s 最长的前缀回文子串 s[:i],然后在前面添加 s[i:][::-1] 即可
  • 与回文相关,首先想到 Manacher 算法,O(N) 时间完成

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def shortestPalindrome(self, s: str) -> str:
        def manacher(s):
            n = len(s)
            A, B = [], [1]*n
            mid, r = 0, 0
            for i in range(n):
                a = min(A[2*mid-i], r-i) if r>i else 0
                while i-a and i+a<n-1 and s[i-a-1]==s[i+a+1]:
                    a += 1
                    B[i+a] = max(B[i+a],a*2+1)
                A.append(a)
                if i+a>r:
                    mid, r = i, i+a
            return B       # B[i]:i结尾的最大回文子串长度(奇数)
        B = manacher('#'+'#'.join(s)+'#')
        i = max(i for i,b in enumerate(B) if b==i+1)//2
        return s[i:][::-1]+s

171 ms