647. 回文子串

给你一个字符串 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[i][j] 表示子串 s[i...j] 是否是回文串，不是 s[i...j] 中最长回文子串的长度！

状态转移方程：当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时，dp[i][j]=true，否则为false

因为 dp[i][j] 依赖于 dp[i+1][j-1]，所以我们需要倒序遍历 i，然后正序遍历 j。

class Solution {
    public int countSubstrings(String s) {
        // 动态规划表，用来记录从 i 到 j 的子字符串是否为回文，重点，不要设计成从i到j的回文串的个数！
        boolean[][] dp = new boolean[s.length()][s.length()];
        // 初始化答案
        int ans = 0;

        // 遍历所有子字符串的起始点 i，从右向左
        for (int i = s.length() - 1; i >= 0; i--) {
            // 遍历所有子字符串的结束点 j，从左向右
            for (int j = i; j < s.length(); j++) {
                // 检查子字符串 s[i..j] 是否为回文
                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    ans++;
                }
            }
        }

        // 返回回文子字符串的数量
        return ans;
    }
}

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。

双指针中心扩展，贪心

class Solution {
    public int countSubstrings(String s) {
        // 初始化回文子串的计数器
        int count = 0;

        // 遍历字符串的每一个字符作为回文中心
        for (int i = 0; i < s.length(); i++) {
            // 搜索以 s[i] 为中心的回文子串的个数（奇数长度）
            count += find(s, i, i);
            // 搜索以 s[i] 和 s[i+1] 为中心的回文子串的个数（偶数长度）
            // 当i=s.length-1时，i+1会越界，但是不能跳过i=s.length-1，因为上面的没越界
            count += find(s, i, i + 1);
        }
        
        // 返回回文子串的数量
        return count;
    }

    // 通过中心扩展法查找原字符串中以left和right为中心的回文子串的个数
    private int find(String s, int left, int right) {
        // 初始化计数器
        int count = 0;

        // 扩展左右指针查找回文
        while (0 <= left && right < s.length() && s.charAt(left) == s.charAt(right)) {
            // 找到一个回文子串，计数加1。重点。
            count++;
            // 向两侧扩展
            left--;
            right++;
        }
        
        // 返回当前中心的回文子串数量
        return count;
    }
}

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(1)$。