一.前言
今天介绍一道相对简单的练习题，同样是来自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;
}
}
网友评论