题目：647. 回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”
示例 2：
输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
方式一：动态规划
定义：函数dp[i][j]代表从下标i到下标j这一段是否是回文子串，值为true、false
动态转移方程：假如下标i对应的字符与下标j对应的字符相等，那位置的结果就要看下标i+1与下标j-1对应的字符的关系，即dp[i][j] = dp[i+1][j-1]; 还要注意两个下标之间的长度，假如 j - i < 2，说明此时两个字符是相邻的，那此时dp[i][j] = true。
/**
* 时间复杂度：O(n^2)
* 空间复杂度：O(n^2)
*/
public int countSubstrings(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
int result = 0;
// 下标i在前，j在后
for (int j = 0; j < s.length(); 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;
result++;
}
}
}
return result;
}方法二：中心扩展法
枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展。但要考虑一个问题：这个中心是一个字符还是两个字符。所以这两种情况都需要考虑。
/**
* 时间复杂度：O(n^2)
* 空间复杂度：O(1)
*/
class Solution {
public int countSubstrings(String s) {
int n = s.length();
int ans = 0;
// 逐个字符进行中心扩展，ans代表总回文子串的数目
for (int center = 0; center < n; center++) {
// 这里有两种情况：
// 1是单个字符为中心，往两边扩展
// 2是以两个字符为中心，往两边扩展
ans += expand(s, center, center) + expand(s, center, center + 1);
}
return ans;
}
private int expand(String s, int left, int right) {
int ans = 0;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
ans++;
left--;
right++;
}
return ans;
}
}