題目

給你一個字符串?s?，請你統計并返回這個字符串中?回文子串?的數目。

回文字符串?是正著讀和倒過來讀一樣的字符串。

子字符串?是字符串中的由連續字符組成的一個序列。

具有不同開始位置或結束位置的子串，即使是由相同的字符組成，也會被視作不同的子串。

示例 1：

輸入：s = "abc"
輸出：3
解釋：三個回文子串: "a", "b", "c"

示例 2：

輸入：s = "aaa"
輸出：6
解釋：6個回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

• 1 <= s.length <= 1000
• s?由小寫英文字母組成

解答

源代碼

class Solution {public int countSubstrings(String s) {int res = 0;for (int i = 0; i < 2 * s.length() - 1; i++) {int left = i / 2, right = left + i % 2;while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {left--;right++;res++;}}return res;}
}

總結

選取符合回文的字符作為子串中心向外擴展，子串分為兩種——單數和雙數，單數中心是一個字符，雙數中心是兩個字符。一個字符串（長度為n）有n個單字符，n-1個雙字符，通過歸納得到左右字符索引，然后不斷向兩邊擴展，不斷更新結果。