总结

本章先从最简单的验证回文开始讲起，分别讲述了字符串、链表和数字的回文验证。接着，讲解如何使用中心扩展法解决最长回文子串问题，并使用动态规划解决最长回文子序列问题，这两种算法都很常见。最后讲解了一道在力扣（LeetCode）上难度级别为困难的题目——超级回文数，来加深我们对回文的理解，实际上这道题并不难，验证数字回文加上剪枝即可。

回文并不是一种算法，回文题目中的算法也千差万别，但是了解回文的性质，并能够判断回文是解决回文问题的基础。还有一种查找一个字符串的最长回文子串的方法，与我们介绍的中心扩展法不同，这是一种线性时间的算法。它就是Manacher's Algorithm（见参考链接/正文[9]），由一个叫Manacher的人在1975年发明。这个方法的最大贡献在于将时间复杂度优化为线性的。还有一种和Manacher's Algorithm类似的算法，叫作Rabin-Karp算法（见参考链接/正文[10]），这个方法也可以将时间复杂度优化为线性的，并且理解起来更容易，但是相对来说局限性也更大，这里就不展开讲解了，感兴趣的读者可以研究一下这两种算法。