这道题属于一道中等题，看来又得背题了，直接看题解吧，有两种解法
第一种动态规划法
状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串
状态转移方程：当s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])时，dp[i][j] = true,否则为false
根据dp[i][j]含义可以画出如下的表格
这个状态转移方程该如何理解呢？主要有以下三点：
1.单个字符肯定是一个回文串，即s[i] == s[j] && j - i == 0
2.当有两个相同的字符时，也是一个回文串，即s[i] == s[j] && j - i == 1
3.当有多个字符时，我们需要把其分成多个区间分别进行判断，那么大区间里肯定包含着小区间，最小区间就是一个字符（[0,0]），大区间也是由一个最小区间然后分别往其左右两端加字符进行组合而成的，所以如果要判断一个大区间字符串是否是回文，那么首先就要判断其里面的小区间，举个例子，比如ababa这个字符串记作区间[0,4],里面的bab记作区间[1,3]，我们会发现如果区间[1,3]是回文串，那么左右各加一个相等的字符，区间[0,4]必定也是回文串，所以当s[i] == s[j]时，要先看区间[i + 1][j - 1]是不是一个回文串，即dp[i + 1][j - 1]是否为true
动态规划代码如下
class Solution {
public int countSubstrings(String s) {
//定义dp这个具有特殊含义的二维数组
boolean[][] dp = new boolean[s.length()][s.length()];
//用于记录符合回文的子串个数
int ans = 0;
//遍历字符串所有区间，i表示区间的左端，j表示区间的右端
for (int j = 0; j < s.length(); j++) {
//i 始终是小于等于 j
for (int i = 0; i <= j; i++) {
//利用状态转移方法判断当前区间是否是回文
if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
ans++;
}
}
}
return ans;
}
}第二种中心扩展法
思路和动态规划类似，比如对一个字符串 ababa，以最中间的 a 作为中心点，往两边扩散，第一次扩散发现 left 指向的是 b，right 指向的也是 b，所以是回文串，继续扩散，同理 ababa 也是回文串。这个只是以最中间的 a 作为中心点，中心点有很多，然后我们只要寻找到所有的中心点并往两边扩散，扩散结束的条件就是边界和left、right指向的字符是否相等
字符串长度要么是奇数或者偶数，所以中心点也是奇数或者偶数，又因为奇数表示为2*n + 1,偶数表示为2*n + 2，所以如果是奇就是一个字符，偶就是两个字符，代码如下
class Solution {
public int countSubstrings(String s) {
// 获取字符串长度
int len = s.length();
// 因为单个字符也是回文，所以把字符串的长度赋值给ans
int ans = len;
// 遍历字符串，以单个字符向两边扩散
for (int i = 0; i < len; i++) {
// left指向中心点的左边一个字符
int left = i - 1;
// right指向中心点的右边的一个字符
int right = i + 1;
// 如果两边字符相等则继续扩散，直到越界或者两边的字符不相等
while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
// 回文数加一
ans++;
// 向左移动
left--;
// 向右移动
right++;
}
}
// 以两个字符向两边扩散，这里i < len - 1,因为只判断了left >= 0,避免让left越界
for (int i = 0; i < len - 1; i++) {
// 由于中心点是两个字符组成，则left指向中心点的其中一个，即左则那个
int left = i;
// right指向中心点右则那个
int right = i + 1;
如果两边字符相等则继续扩散，直到越界或者两边的字符不相等
while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
// 回文数加一
ans++;
// 向左移动
left--;
// 向右移动
right++;
}
}
return ans;
}
}
