[数据结构与算法]剑指offer20：回文子字符串个数

题目：
给定一个字符串，请问该字符串中有多少个回文连续子字符串？例如，字符串“abc”有3个回文子字符串，分别是“a”，“b”，“c”，而字符串“aaa”有6个回文子字符串，分别是“a”，“a”，“a”，“aa”，“aa”，“aaa”。
分析：
还是使用双指针，不同于19题双指针由外向里移动，该题的思路是以一个字符或两个字符为对称中心（回文字符串的长度既可以是奇数也可以是偶数，长度为奇数的回文对称中心只有一个字符，而长度为偶数的回文的对称中心有两个字符），双指针由里向外移动来统计有多少个连续子字符串，具体直接看代码就能明白。
属于两个嵌套的循环，时间复杂度是O（n ^2）,空间复杂度为O(1)。

public class CountSubstrings {
    public static void main(String[] args) {
        String s = "aaa";
        int i = countSubstrings(s);
        System.out.println(i);
    }
    public static int countSubstrings(String s){
//s == null; 也就是s还没有占用存储空间。
//s.length == 0; s占用存储空间，但是其中还没有元素。
        if (s == null ||s.length() == 0){
            return 0;
        }
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
        //第i个字符本身可以成为长度为奇数的回文子字符串对称中心
            count += countPalindrome(s,i,i);
        //第i个字符和第i+1个字符可以一起成为长度为偶数的回文子字符串的对称中心
            count += countPalindrome(s,i,i+1);
        }
        return count;
    }

    private static int countPalindrome(String s,int start,int end) {
        int count = 0;
        while (start>=0 && end <s.length()&&s.charAt(start)==s.charAt(end)){
            count++;
            start--;
            end++;
        }
        return count;
    }
}