本文共 1001 字，大约阅读时间需要 3 分钟。

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

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：“abc”

输出：3

解释：三个回文子串: “a”, “b”, “c”

示例 2：

输入：“aaa”

输出：6

解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

解题思路来自中心点：

比如对一个字符串 ababa，选择最中间的 a 作为中心点，往两边扩散，第一次扩散发现 left 指向的是 b，right 指向的也是 b，所以是回文串，继续扩散，同理 ababa 也是回文串。

这个是确定了一个中心点后的寻找的路径，然后我们只要寻找到所有的中心点，问题就解决了。

中心点一共有多少个呢？看起来像是和字符串长度相等，但你会发现，如果是这样，上面的例子永远也搜不到 abab，想象一下单个字符的哪个中心点扩展可以得到这个子串？似乎不可能。所以中心点不能只有单个字符构成，还要包括两个字符，比如上面这个子串 abab，就可以有中心点 ba 扩展一次得到，所以最终的中心点由 2 * len - 1 个，分别是 len 个单字符和 len - 1 个双字符。

如果上面看不太懂的话，还可以看看下面几个问题：

• 为什么有 2 * len - 1 个中心点？
  aba 有5个中心点，分别是 a、b、c、ab、ba
  abba 有7个中心点，分别是 a、b、b、a、ab、bb、ba

• 什么是中心点？
  中心点即 left 指针和 right 指针初始化指向的地方，可能是一个也可能是两个

• 为什么不可能是三个或者更多？
  因为 3 个可以由 1 个扩展一次得到，4 个可以由两个扩展一次得到
  Java

class Solution {
       public int countSubstrings(String s) {
           // 中心点扩展		int res = 0;		// 中心点遍历		for(int counter=0;counter<2*s.length()-1;counter++) {
   			int left = counter/2;			int right = left + counter%2;						// 判断是否为回文串			while(left>=0&&right

转载地址：https://codingchaozhang.blog.csdn.net/article/details/110674007 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！