一、题目描述

给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。

回文字符串是正着读和倒过来读一样的字符串。

子字符串是字符串中的由连续字符组成的一个序列。

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

示例 1：

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

示例 2：

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

提示：

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

二、思路讲解及代码实现

1、枚举

最容易想到的方法就是枚举出所有子串，然后依次判断它是不是回文字串。

class Solution {
    public int countSubstrings(String s) {

        int len = s.length();
        if(len <= 1){
            return len;
        }

		//记录回文串的个数
        int count = 0;
		//枚举所有的字串
        for(int i=0; i<len; i++){
            for(int j=i; j>=0; j--){
                if(isHuiwen(s, i, j)){
                    count++;
                }
            }
        }
        return count;
    }

	//判断字串是否回文
    boolean isHuiwen(String s, int i, int j){
        int ii = j;
        int jj = i;

        while(ii<=jj){
            if(s.charAt(ii) != s.charAt(jj)){
                return false;
            }
            ii++;
            jj--;
        }
        return true;
    }
}

时间复杂度： O(N^3)

空间复杂度： O(1)

2、中心拓展

从中心开始向两端扩展，如果两端的字符不相等，说明不回文。

这里需要注意一个问题：奇数长度的回文串，中心为一个字符；而偶数长度的字符串，中心为两个字符，这需要分开考虑。而其实也可以将这两种情况合并在一个循环内。

class Solution {
    public int countSubstrings(String s) {

        int len = s.length();
        if(len <= 1){
            return len;
        }

        //回文串的个数
        int count = 0;
        
        //计算奇数长度的回文串
        for(int i=0; i<len; i++){
            int left = i;
            int right = i;
            while(left>=0 && right<len && s.charAt(left)==s.charAt(right)){
                count++;
                left--;
                right++;
            }
        }
        //计算偶数长度的回文串
        for(int i=0; i<len-1; i++){
            int j = i+1;
            int left = i;
            int right = j;
            while(left>=0 && right<len && s.charAt(left)==s.charAt(right)){
                count++;
                left--;
                right++;
            }
        }
        return count;
    }
}

时间复杂度： O(N^2)

空间复杂度： O(1)

文章由极客之家整理，本文链接：https://www.bmabk.com/index.php/post/125002.html