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

题目

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1： 输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”

示例 2：
输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示：

  • 1 <= s.length <= 1000
  • s 由小写英文字母组成

注意：本题与主站647题相同

题解

public int countSubstrings(String s) {
    int len = s.length(), result = 0;
    // 保存区间子字符串是否是回文字符串
    boolean[][] dp = new boolean[len][len];

    for (int i = 0; i < len; i++) {
        for (int j = 0; j <= i; j++) {
            // 若首尾字母相同 判断去掉首尾区间是否是回文字符串
            // 若中间有0个或者1个字符，则肯定是回文字符串
            // 否则 需要判断中间区间子字符串是否是回文
            if (s.charAt(i) == s.charAt(j) && (i - j <= 1 || dp[j + 1][i - 1])) {
                dp[j][i] = true;
                result++;
            }
        }
    }

    return result;
}