剑指 Offer II 020. 回文子字符串的个数

动态规划

1. 回文串采用动态规划，则 dp 数组一般是 boolean[i][j]，表示子串 (i, j) 是否能构成回文串。
2. 回文串数组遍历也是有讲究的，因为 dp[i][j] 是由 dp[i + 1][j - 1] 推导出来的，即从左下角推导出来。因此，遍历数组的时候我们从底向上，从左到右遍历。
3. 子串 (i, j) 为 true 的最基本条件是 s(i) == s(j)，然后判断是否为单个字符串，即 j - i < 2 或子串 s(i + 1, j - 1) 也是回文串。
4. base case 没有特别的要求，保持原状即可。

这题主要有以下考点：

1. dp[] 数组的定义：boolean dp[i][j] 表示子串 [i, j] 是否为回文字符串。
2. 状态转移方程：dp[i][j] == true 的条件是 s[i] == s[j] && (j - i < 2 || dp[i+1][j-1])
3. 二维数组遍历顺序。由于 (i,j) 的结果需要由 (i+1, j-1) 提供， 也就是说第 i 层的数据需要第 i+1 层提供，那么遍历顺序就是从底向上，从左到右。
4. 遍历区域，属于二维数组的右上半部分。如下图所示：
5. 初始化，这里一般是斜对角线都应该为 true，应该是它本身嘛，但是这里有 j - i < 2 的限制，所以可以不用初始化了。

class Solution {
    public int countSubstrings(String s) {
        // 回文串的个数
        if (s == null || s.length() == 0) return 0;
        int res = 0, len = s.length();
        boolean[][] dp = new boolean[len][len];
        // dp[i][j]：[i, j]子串是否为回文串
        // 当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) dp[i][j] == true, ans + 1
        // base case
        int result = 0;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    result++;
                }
            }
        }
        return result;
    }
}

中心扩散

思想：

1. 可以增加遍历的长度以达到一次遍历的效果
2. 一次遍历需要明确 left、right 和 i 三者之间的关系：
   1. left = i / 2
   2. right = left + i % 2：当 i 为偶数时，i % 2 == 0，left 和 right 指向同一个元素（实际数组是奇数个），当 i % 2 != 0时，right 指向 left + 1 （实际数组是偶数个）。

3. 遍历长度为 2 * len - 1：比如 abc，它存在 5 个中心点可以遍历，分别是：a、b、c、ab、bc。

   class Solution {
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) return 0;
        int len = s.length(), count = 0, left = 0, right = 0;
        for (int i = 0; i < 2 * len - 1; i++) {
            left  = i / 2;
            right = left + i % 2;
            // 由中间向两边散开
            while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                count++;
                left--;
                right++;
            }
        }
        return count;
    }
   }