image.png

解法

动态规划解法

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        // i到j是否为回文子串
        boolean[][] dp = new boolean[n][n];
        int res = 0;
        // 递归顺序
        for (int j = 0; j < n; j++) {
            for (int i = 0; i <= j; i++) {
                // 状态转移，i位置等于j，且之前位置是回文串或单个元素
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]);
                if (dp[i][j]) {
                    res++;
                }
            }
        }
        return res;
    }
}

中心扩展思想

class Solution {
    public int countSubstrings(String s) {
        int ans = 0;
        int n = s.length();
        // 中心扩展法，所有字符串都能通过一个元素为中心进行两边同时扩展
        // 或者以两个元素为中心，进行两边同时扩展
        for (int i = 0; i < 2 * n - 1; i++) {
            // left总是从中间，偶数是right和left相同，就是一个扩展的情况
            // 奇数时right比left大1，是二个向外扩展的情况
            int left = i / 2;
            int right = left + i % 2;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                ans++;
                left--;
                right++;
            }        
        }
        return ans;
    }
}