1. 题目

2. 思路

(1) 动态规划

• dp[i][j]表示字符串s的下标为[i,j]的子串是否是回文子串。
• 当chars[i]==chars[j]且下标为[i+1,j-1]的子串是回文子串时，可判定下标为[i,j]的子串也是回文子串，即dp[i][j]=true。

3. 代码

public class Test {public static void main(String[] args) {}
}class Solution {public int countSubstrings(String s) {char[] chars = s.toCharArray();int n = chars.length;boolean[][] dp = new boolean[n][n];int count = 1;dp[n - 1][n - 1] = true;for (int i = n - 2; i >= 0; i--) {dp[i][i] = true;count++;if (chars[i] == chars[i + 1]) {dp[i][i + 1] = true;count++;}for (int j = i + 2; j < n; j++) {if (chars[i] == chars[j] && dp[i + 1][j - 1]) {dp[i][j] = true;count++;}}}return count;}
}