一.前言
今天介紹一道相對(duì)簡(jiǎn)單的練習(xí)題叉橱，同樣是來(lái)自LeetCode儒飒。
示例1：
輸入：s = "abc"
輸出：3
解釋：三個(gè)回文子串: "a", "b", "c"
示例2：
輸入：s = "aaa"
輸出：6
解釋：6個(gè)回文子串: "a", "a", "a", "aa", "aa", "aaa"
題目來(lái)源：LeetCode
二.題解
其實(shí)關(guān)于回文的題有很多種，而解法更是多種多樣隘弊，今天介紹兩種方法哈踱，遞歸和中心拓展。
1.遞歸
簡(jiǎn)單來(lái)說(shuō)遞歸就是一個(gè)函數(shù)調(diào)用自己本身的行為就叫遞歸梨熙。遞歸具有代碼簡(jiǎn)潔开镣，易讀的特點(diǎn)，但是缺點(diǎn)也不容忽視：
a).運(yùn)行效率較低咽扇。
b).可能會(huì)導(dǎo)致棧溢出邪财，如果遞歸次數(shù)太多陕壹，需要在內(nèi)存棧中分配空間以保存參數(shù)以及臨時(shí)變量就會(huì)過(guò)多，當(dāng)超出棧的容量树埠，就會(huì)導(dǎo)致棧溢出糠馆。
我們思路是這樣的：首先通過(guò)遍歷找到所有的子串，然后再判斷子串是否是回文怎憋。那么怎么判斷是否是回文呢又碌？比如這樣的一個(gè)字符串abcba,我們判斷其是否為回文，可以先判斷第一個(gè)和最后一個(gè)字符是否相同绊袋，再判斷第二個(gè)字符和倒數(shù)第二個(gè)字符是否相同...直到全部判斷完畢毕匀，這個(gè)過(guò)程中，我們反復(fù)做著相同的工作癌别，因此可以使用遞歸皂岔，來(lái)看看代碼吧：
class Solution {
public int countSubstrings(String s) {
int result = 0;//最終結(jié)果
//兩層循環(huán)展姐，從字符串首部開(kāi)始遍歷處所有子字符串
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
//每個(gè)子字符串調(diào)用isHuiwen凤薛，若返回 true 則 result + 1
if (isHuiwen(s, i, j)) {
result++;
}
}
}
return result;
}
//isHuiwen需要三個(gè)參數(shù)，s 是字符串诞仓，i 是子字符串第一個(gè)字符缤苫，j 是子字符串的最后一個(gè)字符
public static boolean isHuiwen(String s, int i, int j) {
//兩種情況返回true（1,2）
//1.當(dāng)子字符串的長(zhǎng)度是奇數(shù)時(shí)，此時(shí)回文中心只有一個(gè)墅拭，當(dāng)遞歸到 i == j時(shí)活玲，說(shuō)明全部首尾字符判斷完畢，全部相等谍婉，返回true
if (i == j) return true;
else {
if (s.charAt(i) != s.charAt(j)) {
//如果二者不相等舒憾，直接返回false，退出遞歸
return false;
} else {
//2.當(dāng)子字符串的長(zhǎng)度為偶數(shù)穗熬，此時(shí)回文中心是兩個(gè)字符镀迂，由于上面的if中已經(jīng)判斷 i 和 j是相同的
//因此到這里也將首尾字符全部判斷完畢，全部相等唤蔗，返回true
if (i + 1 == j) {
return true;
} else return isHuiwen(s, ++i, --j);
//如果程序走到這兒探遵，說(shuō)明不滿足上面任意一種情況，因此在調(diào)用函數(shù)進(jìn)一步判斷 ++i 和 --j 是否相等
}
}
}
}
我們上面這種方法找出子字符串需要兩層循環(huán)妓柜，時(shí)間復(fù)雜度為O(n^2) 而判斷它是否為回文又是O(n)箱季，因此總的復(fù)雜度為O(n^3)。顯然效率不高棍掐，那我們?cè)賮?lái)看看LeetCode官方題解吧藏雏！——中心拓展
2.中心拓展
大致思路：我們從每一個(gè)可能成為回文中心的點(diǎn)開(kāi)始，若前后字符相等就拓展作煌，反之掘殴，則停止拓展赚瘦。
當(dāng)子字符串是奇數(shù)時(shí)，回文中心是一個(gè)奏寨；當(dāng)子字符串是偶數(shù)個(gè)時(shí)起意，回文中心是兩個(gè)。有沒(méi)有一種方法可以統(tǒng)一二者呢服爷？答案是有的杜恰。通過(guò)規(guī)律我們可以發(fā)現(xiàn)：無(wú)論子字符串長(zhǎng)度是偶數(shù)還是奇數(shù)获诈，我們都需要遍歷 2n - 1 次字符串仍源，換句話說(shuō)就是有 2n - 1 個(gè)回文中心，
class Solution {
public int countSubstrings(String s) {
int n = s.length(), ans = 0;
for (int i = 0; i < 2 * n - 1; ++i) {
//向前拓展從i開(kāi)始舔涎，向后拓展從r開(kāi)始
int l = i / 2, r = i / 2 + i % 2;
//當(dāng)子字符串個(gè)數(shù)為偶數(shù)時(shí)笼踩，i 和 r 相等
while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
//當(dāng)前后字符相等且 i 和 r 未越界時(shí)
//開(kāi)始向兩邊拓展
--l;
++r;
++ans;
}
}
return ans;
}
}
