offer2-20

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

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

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

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

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        Boolean[][] valid = new Boolean[s.length()][s.length()];

        return getCount(valid, s, s.length() - 1);
    }

    private int getCount(Boolean[][] valid, String s, int index) {
        int count = 0;

        if (index == 0) {
            return 1;
        }

        for (int i = 0; i <= index; i++) {
            if (isValid(valid, i, index, s)) {
                count++;
            }
        }

        return count + getCount(valid, s, index - 1);
    }


    private boolean isValid(Boolean[][] valid, int from, int to, String s) {
        if (valid[from][to] != null) {
            return valid[from][to];
        }
        boolean isValid = false;
        if (from == to) {
            isValid = true;
        } else if (from + 1 == to) {
            isValid = s.charAt(from) == s.charAt(to);
        } else {
            isValid = (s.charAt(from) == s.charAt(to)) && isValid(valid, from + 1, to - 1, s);
        }

        valid[from][to] = isValid;
        return isValid;
    }
}
//leetcode submit region end(Prohibit modification and deletion)