📃 题目描述

题目链接：

• 剑指 Offer II 020. 回文子字符串的个数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 647. 回文子串 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

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

示例 1：

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

示例 2：

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

🔔 解题思路

暴力

双重循环，时间复杂度 O(N^2)

class Solution {
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        // 回文子串的个数
        int count = 0;
        for (int i = 0; i < s.length(); i ++) {
            for (int j = i; j < s.length(); j ++) {
                if (isPalindrome(s, i, j)) {
                    count ++;
                }
            }
        }

        return count;
    }

    // 左闭右闭
    private boolean isPalindrome(String s, int left, int right) {
        if (left == right) {
            return true;
        }

        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left ++;
            right --;
        }

        return true;
    }
}

左右指针

前面判断回文的题目都是从字符串的两端开始向里移动指针来判断字符串是否是一个回文，其实也可以换一个方向从字符串的中心开始向两端延伸。

如果存在一个长度为 m 的回文子字符串，则分别再向该回文的两端延伸一个字符，并判断回文前后的字符是否相同。如果相同，就找到了一个长度为 m+2 的回文子字符串。

例如，在字符串"abcba"中，从中间的"c"出发向两端延伸一个字符，由于"c"前后都是字符'b'，因此找到了一个长度为3的回文子字符串"bcb"。然后向两端延伸一个字符，由于"bcb"的前后都是字符'a'，因此又找到一个长度为5的回文子字符串"abcba"。

值得注意的是，回文的长度既可以是奇数，也可以是偶数。长度为奇数的回文的对称中心只有一个字符，而长度为偶数的回文的对称中心有两个字符。

class Solution {
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        // 回文子串的个数
        int count = 0;
        for (int i = 0; i < s.length(); i ++) {
            // 奇数，以 s[i] 为中心
            count += countPalindrome(s, i, i);
            // 偶数，以 s[i] 和 s[i + 1] 为中心
            count += countPalindrome(s, i, i + 1);
        }

        return count;
    }

    // 左闭右闭(以 left 和 right 为中心分别向左右两边拓展)
    private int countPalindrome(String s, int left, int right) {
        // 回文子串的个数
        int count = 0;

        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) == s.charAt(right)) {
                // 向左拓展
                left --;
                // 向右拓展
                right ++;

                count ++;
            }
            // 一旦发现不一样，则直接 break，至此是以 left 和 right 为中心能找到的最长回文串了
            else {
                break;
            }
        }

        return count;
    }
}

时间复杂度也是 O(N^2)

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：