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;}
}