力扣HOT100/最长回文子串

比较难懂的一道题，我看题解看了半天才想明白
题目链接
第一想法是暴力枚举所有的子串，然后判断是否回文，但是太过复杂，判断子串回文要$O(n)$,一共有$O(n ^ 2)$的子串，整体的时间复杂度就是$O(n ^ 3)$ ，有点慢

方法一：中心扩展法

回文串无论长短都是中心对称的，这个方法就是遍历中心，然后不断扩展，唯一注意的就是回文串长度是奇数还是偶数，奇数是以字符为中心，而偶数就是以字符间的缝隙为中心，所以循环遍历的条件是i < 2 * n - 1

方法二：Manacher算法