最短回文串解题思路分享

在算法学习中，如果想挑战高难度的算法题，可以尝试挑战下这道题：

常规做法：

class Solution:def shortestPalindrome(self, s):""":type s: str:rtype: str"""ss=s[::-1]n=len(ss)for i in range(len(s),-1,-1):if ss[n-i:]==s[:i]:breakreturn (ss[:n-i]+s)

可使用 Manacher 和 KMP， Manacher 算法是求最长回文子串非常漂亮的算法了。本题目可以转换为求给定字符串从首字母开始的最长回文子串（然后将余下的 reverse，insert 到头部就可以），而求从首字母开始的最长回文子串，可以用 Manacher 算法，也可以将 str 反转以后拼接到 str 尾部，使用 KMP 的求 next 数组，这样 next 数组最后一个值就是从首字母出发的最长回文子串长度。

写在最后

解题方法千变万化，重在思考的过程，并非答案。许多实战过的小伙伴相信也在面试大厂的岗位时，了解面试官其实并不关心最终结果，而是需要你提供自己的理解和思路。