题目链接

参考链接

https://leetcode-cn.com/problems/shortest-palindrome/solution/shi-jian-fu-za-du-on-jie-fa-la-che-by-time-limit/

方法1 常规思路 模拟

回文串 由 原本字符串和字符串中的子串逆序组成
因此从字符串的逆序中寻找最短子串 使得字符串能够构成回文串

image.png

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        if not s:
            return s
        def isHuiwen(s):
            pre=s[len(s)//2:]
            suf=s[:(len(s)+1)//2][::-1]
            # print('    ',pre,suf)
            if pre==suf:
                return True
            else:
                return False
        
        for i in range(len(s)):
            t=s[::-1][:i]
            # print(t,t+s,isHuiwen(t+s))
            if isHuiwen(t+s):
                return t+s

方法2 Manacher