Listen to the pain. It's both history teacher and fortune teller.
倾听你的痛苦。痛苦是历史老师，也是预言家。
问题描述
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
-
输入的字符串长度不会超过 1000 。
动态规划解决
这题让求一个字符串中有多少个回文子串，子串必须是连续的，子序列可以不连续，这题可以使用动态规划来解决。
定义dp[i][j]：表示字符串s从下标i到j是否是回文串，如果dp[i][j]是true，则表示是回文串，否则不是回文串。
如果要计算dp[i][j]，首先要判断s.charAt(i)==s.charAt(j)是否成立。
1，如果s.charAt(i)!=s.charAt(j)，那么dp[i][j]肯定不能构成回文串。如下图所示
2，如果s.charAt(i)==s.charAt(j)，我们还需要判断dp[i+1][j-1]是否是回文串，如下图所示。
实际上如果i和j离的非常近的时候，比如j-i<=2，我们也可以认为dp[i][j]是回文子串，如下图所示
搞懂了上面的分析过程，递推公式就呼之欲出了。
if (s.charAt(i) != s.charAt(j)) continue;dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
代码我们大致也能写出来了，因为是从i到j，所以j不能小于i。
1 for (int i = 0; i < length; i--) {
2 for (int j = i; j < length; j++) {
3 if (s.charAt(i) != s.charAt(j))
4 continue;
5 dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
6 }
7 }
但是这里有个问题，如果我们想要求dp[i][j]还需要知道dp[i+1][j-1]，如下图所示
对于这个二维数组，如果从上往下遍历当计算dp[i][j]的时候，我们还没有计算dp[i+1][j-1]的值，所以这个时候是没法计算dp[i][j]的，但我们可以从下往上计算，如下所示
1 //从下往上计算
2 for (int i = length - 1; i >= 0; i--) {
3 for (int j = i; j < length; j++) {
4 if (s.charAt(i) != s.charAt(j))
5 continue;
6 dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
7 }
8 }
我们来看下最终代码
1public int countSubstrings(String s) {
2 int length = s.length();
3 boolean[][] dp = new boolean[length][length];
4 int count = 0;//回文串的数量
5 //字符串从后往前判断
6 for (int i = length - 1; i >= 0; i--) {
7 for (int j = i; j < length; j++) {
8 //如果i和j指向的字符不一样，那么dp[i][j]就
9 //不能构成回文字符串
10 if (s.charAt(i) != s.charAt(j))
11 continue;
12 dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
13 //如果从i到j能构成回文串，count就加1
14 if (dp[i][j])
15 count++;
16 }
17 }
18 return count;
19}
我们来看一下他的计算过程，如下图所示，红色箭头表示的是右上角的值依赖左下角的值，这里只画了部分，没画完。黄色表示的是计算的顺序，他是从右下角开始，从下往上，从左往右开始计算的，所以当计算dp[i][j]的时候，dp[i+1][j-1]已经计算过了（图中灰色部分是i>j，属于无效的）
除了上面这种方式以外，我们还可以从左往右，从上往下开始计算，这样也能保证在计算dp[i][j]的时候，dp[i+1][j-1]已经计算过了，如下图所示
来看下代码
1public int countSubstrings(String s) {
2 int length = s.length();
3 boolean[][] dp = new boolean[length][length];
4 int count = 0;//回文串的数量
5 for (int j = 0; j < length; j++) {
6 for (int i = 0; i <= j; i++) {
7 //如果i和j指向的字符不一样，那么dp[i][j]就
8 //不能构成回文字符串
9 if (s.charAt(i) != s.charAt(j))
10 continue;
11 dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
12 //如果从i到j能构成回文串，count就加1
13 if (dp[i][j])
14 count++;
15 }
16 }
17 return count;
18}
上面代码中dp是二维数组，但实际上在计算当前列的时候（如上图所示），我们只会用到上一列的结果，再往之前的就用不到了，所以我们还可以在优化一下，把二维数组改为一维。
1public int countSubstrings(String s) {
2 int length = s.length();
3 boolean[] dp = new boolean[length];
4 int count = 0;//回文串的数量
5 for (int j = 0; j < length; j++) {
6 for (int i = 0; i <= j; i++) {
7 if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1])) {
8 dp[i] = true;
9 count++;
10 } else {
11 dp[i] = false;
12 }
13 }
14 }
15 return count;
16}
中心扩散法解决
中心扩散的思想，是找到一个字符作为回文字符串的中心，往两边扩散，来看个视频
实际上回文串的字符不一定都是奇数个，还有可能是下面这样，所以我们计算的时候不光要考虑奇数的情况，还要考虑偶数的情况
来看下代码。
1//回文串的数量
2int count = 0;
3
4public int countSubstrings(String s) {
5 //边界条件判断
6 if (s == null || s.length() == 0)
7 return 0;
8
9 for (int i = 0; i < s.length(); i++) {
10 //回文的长度是奇数
11 extendPalindrome(s, i, i);
12 //回文是长度是偶数
13 extendPalindrome(s, i, i + 1);
14 }
15 return count;
16}
17
18//以left和right为中心点，求回文字符串的数量
19private void extendPalindrome(String s, int left, int right) {
20 while (left >= 0 && right < s.length() && s.charAt(left--) == s.charAt(right++)) {
21 count++;
22 }
23}
还可以把上面的代码合并一下，如果回文串是奇数，我们把回文串中心的那个字符叫做中心点，如果回文串是偶数我们就把中间的那两个字符叫做中心点。
对于一个长度为n的字符串，我们可以用它的任意一个字符当做中心点，所以中心点的个数是n。我们还可以用它任意挨着的两个字符当做中心点，所以中心点是n-1，总的中心点就是2*n-1。
然后以这2*n-1个中心点为起点，往左右两边查找回文串，来看下代码。
1//中心点的个数
2public int countSubstrings(String s) {
3 //字符串的长度
4 int length = s.length();
5 //中心点的个数
6 int size = 2 * length - 1;
7 //回文串的个数
8 int count = 0;
9 for (int i = 0; i < size; ++i) {
10 //要么left等于right，要么left+1等于right。也就是说如果left等于
11 //right，那么中心点就是一个字符，如果left+1等于right，中心点就是
12 //2个字符
13 int left = i / 2;
14 int right = left + i % 2;
15
16 while (left >= 0 && right < length && s.charAt(left--) == s.charAt(right++))
17 ++count;
18 }
19 return count;
20}
总结
回文字符串前面也讲过很多了，中心扩散法应该是最容易理解的，也是最常见的解回文字符串的一种方式。而对于动态规划要注意dp之间计算的先后顺序。
截止到目前我已经写了500多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有900多页，大家可以在公众号中回复关键字“pdf”即可获取下载链接。