0214：最短回文串（★★）

2015-08-02 约 300 字预计阅读 1 分钟次阅读

力扣第 214 题

题目

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

示例 1：

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

示例 2：

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

提示：

0 <= s.length <= 5 * 10⁴
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

目录

0214：最短回文串（★★）

题目

分析

解答