一、题目描述
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000
s 由小写英文字母组成
二、思路讲解及代码实现
1、枚举
最容易想到的方法就是枚举出所有子串，然后依次判断它是不是回文字串。
class Solution { public int countSubstrings(String s) { int len = s.length(); if(len <= 1){ return len; } //记录回文串的个数 int count = 0; //枚举所有的字串 for(int i=0; i<len; i++){ for(int j=i; j>=0; j--){ if(isHuiwen(s, i, j)){ count++; } } } return count; } //判断字串是否回文 boolean isHuiwen(String s, int i, int j){ int ii = j; int jj = i; while(ii<=jj){ if(s.charAt(ii) != s.charAt(jj)){ return false; } ii++; jj--; } return true; } }
时间复杂度： O(N^3)
空间复杂度： O(1)
2、中心拓展
从中心开始向两端扩展，如果两端的字符不相等，说明不回文。
这里需要注意一个问题：奇数长度的回文串，中心为一个字符；而偶数长度的字符串，中心为两个字符，这需要分开考虑。而其实也可以将这两种情况合并在一个循环内。
class Solution { public int countSubstrings(String s) { int len = s.length(); if(len <= 1){ return len; } //回文串的个数 int count = 0; //计算奇数长度的回文串 for(int i=0; i<len; i++){ int left = i; int right = i; while(left>=0 && right<len && s.charAt(left)==s.charAt(right)){ count++; left--; right++; } } //计算偶数长度的回文串 for(int i=0; i<len-1; i++){ int j = i+1; int left = i; int right = j; while(left>=0 && right<len && s.charAt(left)==s.charAt(right)){ count++; left--; right++; } } return count; } }
时间复杂度： O(N^2)
空间复杂度： O(1)
