给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

回文子串：指的是一个字符串顺序遍历与逆序遍历得到的结果是一样的。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

思路一：暴力破解法

列举所有的可能的子串，并判断其是否为回文子串。

代码如下：

 public int countSubstrings(String s) {int total = s.length();int num = 0;for (int i = 0; i <total ; i++) {for (int j = i+1; j <=total ; j++) {if (isPalindrome(s.substring(i,j))==true) num++;}}return num;}//判断字符串是否为回文子串private Boolean isPalindrome(String s){char[] chars = s.toCharArray();for (int i = 0,j=chars.length-1; i <j ; i++,j--) {if ((chars[i]^chars[j])!=0) return false;}return true;}

思路二： 中心扩展法

从字符串最中心的字符开始向两边扩展，通过比较两边的字符是否相等便能判断该字符串是否为回文字符串。这种方法需要将其分为奇数与偶数两种情况对待，奇数长度的中心是一个字符，偶数长度的中心是两个字符。

代码如下：

 public int countSubstrings2(String s) {int total = s.length();int num = 0;int start = 0;for (int i = 0; i <total ; i++) {int one = 1;while (start-one>=0&&start+one<total&&s.charAt(start-one)==s.charAt(start+one)){num++;one++;}int tow = 0;while (start+tow+1<total&&(start-tow)>=0&&s.charAt(start-tow)==s.charAt(start+tow+1)){num++;tow++;}start++;}return num+total;}

我们可以分别考虑奇数与偶数的情况，其实也可以用一个循环来搞定。假设我们的字符串长度为n=4,可能生成的循环中心的情况如下：

编号 i	回文中心左起始位置 l	回文中心右起始位置 r
0	0	0
1	0	1
2	1	1
3	1	2
4	2	2
5	2	3
6	3	3

通过观察这张表我们可以得出以下结论：
1、长度为n的字符串可以得到2*n-1种回文中心。
2、回文中心的左起始位置与右起始关系与编号的关系为：l = i/2;r = l+ i mod 2

代码如下：

class Solution {public int countSubstrings(String s) {int n = s.length();int num = 0;for (int i = 0; i <2*n-1 ; i++) {int l = i/2;int r = l+i%2;while (l>=0&&r<n&&s.charAt(l)==s.charAt(r)){l--;r++;num++;  }}return num;}
}

思路三：Manacher算法

算法思路

代码如下：

class Solution {public int countSubstrings(String s) {int n = s.length();StringBuffer t = new StringBuffer("$#");for (int i = 0; i < n; ++i) {t.append(s.charAt(i));t.append('#');}n = t.length();t.append('!');int[] f = new int[n];int iMax = 0, rMax = 0, ans = 0;for (int i = 1; i < n; ++i) {// 初始化 f[i]f[i] = i <= rMax ? Math.min(rMax - i + 1, f[2 * iMax - i]) : 1;// 中心拓展while (t.charAt(i + f[i]) == t.charAt(i - f[i])) {++f[i];}// 动态维护 iMax 和 rMaxif (i + f[i] - 1 > rMax) {iMax = i;rMax = i + f[i] - 1;}// 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整ans += f[i] / 2;}return ans;}
}

提示：

输入的字符串长度不会超过 1000 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindromic-substrings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。