字符串：子字符串回文的个数_字符串中回文子串的个数

题目

求一个字符串中其所有子字符串是回文的个数。例如

• “aaa”，其子字符串是回文的包括：a,a,a,aa,aa,aaa.
• “abcba", 是回文的子字符串包括：a,b,c,bcb,abcba,b,a

解题思路

原题可以拆分成几个小问题：

1. 如何得到子字符串？
2. 求回文个数？

子字符串

求子字符串。第一种方法是，之前我们是从字符串两端开始，向里移动双指针，判断区间内是否有回文。而这里我们要采用第二种方法，又字符串中心向外扩散，来求回文。

回文个数

例如字符串s = “abcba”,我们以c中心，指针向左右各移动1位, 得到子字符串“bcb”, 于是我们可知这个是一个回文，长度为3. 接着继续向左右方向移动指针，得到新的回文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++) {    //枚举字符串每个字符，从左到右。
             //以各点为中心，向左右散开求回文。
             count += countPalidrome(s, i, i); //确认中心点
             count += countPalidrome(s, i, i + 1); //考虑回文长度为偶数的情况，确认中心点为两个数
         }
        return count;
    }

    private int countPalidrome(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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

总结

求子字符串回文个数。 可以采取以子字符串中心，向外扩散的方式，移动指针来求回文的个数。需要注意中心点的选取分成回文长度是偶数和奇数两种情况。