本文共 1434 字，大约阅读时间需要 4 分钟。

题目：（困难）

标签：字符串、双指针、递归、KMP算法

这道题就相当于从前往后找字符串中最长的回文串

解法一（暴力解法）：

class Solution:    def shortestPalindrome(self, s: str) -> str:        N = len(s)        for i in range(N, 0, -1):            if s[:i] == s[:i][::-1]:                return s[i:][::-1] + s[:i] + s[i:]        return ""

解法二（双指针递归）：

虽然最坏情况的时间复杂度没有变，但是平均情况的时间复杂度明显下降。

class Solution:    def shortestPalindrome(self, s: str) -> str:        N = len(s)        idx1 = 0        for idx2 in range(N - 1, -1, -1):            if s[idx1] == s[idx2]:                idx1 += 1        if idx1 == N:            return s        return s[idx1:][::-1] + self.shortestPalindrome(s[:idx1]) + s[idx1:]

解法三（KMP算法）：

class Solution:    def shortestPalindrome(self, s: str) -> str:        s_new = s + "#" + s[::-1]        N = len(s_new)        table = [0] * N  # KMP失败函数        length = 0  # 当前匹配字符串长度        i = 1  # 当前坐标        while i < N:            if s_new[length] == s_new[i]:                length += 1                table[i] = length                i += 1            else:                if length > 0:                    length = table[length - 1]                else:                    i += 1                    length = 0        return s[table[-1]:][::-1] + s

转载地址：https://dataartist.blog.csdn.net/article/details/107996539 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！