[LeetCode]Palindromic Substrings

直观的做法就是以每个点为中心向两边展开，然后统计所有回文的个数。时间复杂度最差O(n^2)，常数空间，代码如下：


如果是要记录所有的回文的话，我们是没有更快的办法的，因为无论如何我们都要扫到每一个回文。但是统计总数的话就不一样了，我们之前在这篇文章介绍过manacher算法，我们可以线性时间求最长回文。算法中我们用数组r[i]记录以i位置为中心的回文的最大半径，根据这个半径，我们自然也可以求出以i位置为中心的回文有多少个。时间复杂度O(n)，空间复杂度O(n)，代码如下：