【leetcode】回文子字符串的个数

一、题目描述

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

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

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

二、代码思路

使用枚举暴力 + 双指针判断回文串

枚举每一个子字符串。将每个子字符串都传入判断回文串的函数判断即可，是回文串就++。

2.1 中心扩展

遍历字符串，对每个字符，都看作回文的中心，向两端延申进行判断直到非回文。

回文的中心可能是一个字符，也可能是两个字符。

注意双指针可能越界。

转载于：剑指offer官方题解

三、 代码题解

class Solution {
    public boolean isPalind(int i, int j, String s) {
        int l = i;
        int r = j;
        while(l < r) {
            if(s.charAt(l) != s.charAt(r)) {
                return false;
            } else{
                l++;
                r--;
            }
        }
        return true;
    }
    public int countSubstrings(String s) {
        //1 <= s.length <= 1000 , s 由小写英文字母组成
        //所以O(N2) 复杂度也不会超时
        int res = 0;
        if(s.length() == 1) return 1;
        for(int i = 0; i < s.length(); i++) {
            for(int j = i + 1; j < s.length(); j++) {
                //注意 ++res 和 res++的区别 
                res = isPalind(i, j, s) ? ++res : res;
            }
        }
        return res + s.length();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

时间复杂度： O(N3)

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

所以O(N3) 复杂度也基本上有可能过

中心扩展：

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) {
            count += countPalindrome(s, i, i);
            count += countPalindrome(s, i, i+1);
        }
        return count;
    }

    //从字符串的第start位置向左，end位置向右，比较是否为回文并计数
    private 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;
    }
}

作者：ling-han-i
链接：https://leetcode.cn/problems/a7VOhD/solution/jian-zhi-offer-zhuan-xiang-tu-po-ban-gua-6bln/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30