算法练习：回文子字符串的个数（多种方法）

一.前言

今天介绍一道相对简单的练习题，同样是来自LeetCode。

回文子字符串的个数，给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例1：

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

示例2：

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

题目来源：LeetCode

二.题解

其实关于回文的题有很多种，而解法更是多种多样，今天介绍两种方法，递归和中心拓展。

1.递归

简单来说递归就是一个函数调用自己本身的行为就叫递归。递归具有代码简洁，易读的特点，但是缺点也不容忽视：

a).运行效率较低。
b).可能会导致栈溢出，如果递归次数太多，需要在内存栈中分配空间以保存参数以及临时变量就会过多，当超出栈的容量，就会导致栈溢出。

我们思路是这样的：首先通过遍历找到所有的子串，然后再判断子串是否是回文。那么怎么判断是否是回文呢？比如这样的一个字符串abcba,我们判断其是否为回文，可以先判断第一个和最后一个字符是否相同，再判断第二个字符和倒数第二个字符是否相同...直到全部判断完毕，这个过程中，我们反复做着相同的工作，因此可以使用递归，来看看代码吧：

class Solution {
    public int countSubstrings(String s) {
        int result = 0;//最终结果
        //两层循环，从字符串首部开始遍历处所有子字符串
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                //每个子字符串调用isHuiwen，若返回 true 则 result + 1
                if (isHuiwen(s, i, j)) {
                    result++;
                }
            }
        }
        return result;
    }
    //isHuiwen需要三个参数，s 是字符串，i 是子字符串第一个字符，j 是子字符串的最后一个字符
    public static boolean isHuiwen(String s, int i, int j) {
        //两种情况返回true（1,2）
        //1.当子字符串的长度是奇数时，此时回文中心只有一个，当递归到 i == j时，说明全部首尾字符判断完毕，全部相等，返回true
        if (i == j) return true;
        else {
            if (s.charAt(i) != s.charAt(j)) {
                //如果二者不相等，直接返回false，退出递归
                return false;
            } else {
                //2.当子字符串的长度为偶数，此时回文中心是两个字符，由于上面的if中已经判断 i 和 j是相同的
                //因此到这里也将首尾字符全部判断完毕，全部相等，返回true
                if (i + 1 == j) {
                    return true;
                } else return isHuiwen(s, ++i, --j);
                //如果程序走到这儿，说明不满足上面任意一种情况，因此在调用函数进一步判断 ++i 和 --j 是否相等
            }
        }
    }
}

我们上面这种方法找出子字符串需要两层循环，时间复杂度为O(n^2) 而判断它是否为回文又是O(n)，因此总的复杂度为O(n^3)。显然效率不高，那我们再来看看LeetCode官方题解吧！——中心拓展

2.中心拓展

大致思路：我们从每一个可能成为回文中心的点开始，若前后字符相等就拓展，反之，则停止拓展。

当子字符串是奇数时，回文中心是一个；当子字符串是偶数个时，回文中心是两个。有没有一种方法可以统一二者呢？答案是有的。通过规律我们可以发现：无论子字符串长度是偶数还是奇数，我们都需要遍历 2n - 1 次字符串，换句话说就是有 2n - 1 个回文中心，

class Solution {
    public int countSubstrings(String s) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < 2 * n - 1; ++i) {
            //向前拓展从i开始，向后拓展从r开始
            int l = i / 2, r = i / 2 + i % 2;
            //当子字符串个数为偶数时，i 和 r 相等 
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                //当前后字符相等且 i 和 r 未越界时
                //开始向两边拓展
                --l;
                ++r;
                ++ans;
            }
        }
        return ans;
    }
}