【区间dp-回文-2】leet647. 回文子串

同：LCR 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 由小写英文字母组成

构建回文dp数组的时候，会统计出现的所有的回文子串。所以这个题目只要在dp[l][r]=true的时候计数即可.

public int countSubstrings(String s) {
        int n=s.length();
        int count=0;
        boolean[][] dp = new boolean[n][n];
        String  ans=s.substring(0,1);
        for (int r = 0; r < s.length(); r++) {
            for (int l = r; l >= 0; l--) {
                if (l == r || s.charAt(l) == s.charAt(r) && (l + 1 == r || dp[l + 1][r - 1] == true)) {
                    dp[l][r] = true;
                    count++;
                }
            }
        }
        return count;
    }