題目
#

leetcode 647 - Palindromic Substrings (題目說明請點連結)

題目簡述
#

給一個字串 s，請計算其中回文子字串的數量。
回文子字串是指正著讀和倒著讀都一樣的字串。例如，“aaa” 和 “aba” 都是回文子字串。

範例
#

Example 1:

Input: s = "abc"
Output: 3
Explanation: 三個回文子字串："a", "b", "c"

Example 2:

Input: s = "aaa"
Output: 6
Explanation: 六個回文子字串："a", "a", "a", "aa", "aa", "aaa"

Example 3:

Input: s = "aba"
Output: 4
Explanation: 四個回文子字串："a", "b", "a", "aba"

解題思路
#

這題要求我們計算字串中回文子字串的數量。我們可以使用中心擴展法（Center Expansion Approach）來解決這個問題，具體方法是對於每個位置，以其為中心向兩邊擴展，檢查是否形成回文。

解法
#

從中心擴展

對於字串中的每個位置 i，以其為中心向兩邊擴展
檢查奇數長度的回文（以單個字符為中心）
檢查偶數長度的回文（以兩個字符之間為中心）
統計所有找到的回文子字串數量

步驟
#

遍歷字串：
- 對於每個位置 i，檢查以該位置為中心的回文
奇數長度回文：
- 以位置 i 為中心，向左右擴展
- 檢查 s[left] == s[right]，其中 left = i-1, right = i+1
偶數長度回文：
- 以位置 i 和 i+1 之間為中心，向左右擴展
- 檢查 s[left] == s[right]，其中 left = i, right = i+1
統計回文：
- 每次找到回文時，計數器加 1
返回結果：
- 返回總的回文子字串數量

例子說明
#

s = "aaa"

步驟	位置 i	中心類型	擴展過程	找到的回文	計數
第 1 步	0	奇數中心	以 ‘a’ 為中心	“a”	1
第 1 步	0	偶數中心	以 ‘a’ 和 ‘a’ 之間為中心	“aa”	2
第 2 步	1	奇數中心	以 ‘a’ 為中心	“a”	3
第 2 步	1	偶數中心	以 ‘a’ 和 ‘a’ 之間為中心	“aa”	4
第 3 步	2	奇數中心	以 ‘a’ 為中心	“a”	5
第 3 步	2	偶數中心	超出邊界	無	5

最終結果： 6

中心擴展過程說明：

位置 0：
- 奇數中心：以 ‘a’ 為中心，找到 “a”
- 偶數中心：以 ‘a’ 和 ‘a’ 之間為中心，找到 “aa”
位置 1：
- 奇數中心：以 ‘a’ 為中心，找到 “a”
- 偶數中心：以 ‘a’ 和 ‘a’ 之間為中心，找到 “aa”
位置 2：
- 奇數中心：以 ‘a’ 為中心，找到 “a”
- 偶數中心：超出邊界，無法擴展

找到的回文子字串： “a”, “a”, “a”, “aa”, “aa”, “aaa”

完整程式碼
#

java

class Solution {
    public int countSubstrings(String s) {
        // 結果計數器
        int res = 0;

        // 遍歷字串中的每個位置
        for(int i = 0; i < s.length(); i++){
            // 檢查以位置 i 為中心的奇數長度回文
            res += countPalindromes(i, i, s);
            // 檢查以位置 i 和 i+1 之間為中心的偶數長度回文
            res += countPalindromes(i, i+1, s);
        }

        // 返回總的回文子字串數量
        return res;
    }

    // 中心擴展方法：計算以 left 和 right 為中心的回文數量
    public int countPalindromes(int left, int right, String s){
        int count = 0;

        // 向左右擴展，檢查是否形成回文
        while(left >= 0 && right <= s.length() - 1 && s.charAt(left) == s.charAt(right)){
            // 找到回文，計數加 1
            count++;
            // 繼續向兩邊擴展
            left--;
            right++;
        }
        
        // 返回以該中心為起點的回文數量
        return count;
    }
}

時間複雜度
#

時間複雜度：O(n²)，其中 n 是字串的長度
- 遍歷字串中的每個位置：O(n)
- 對於每個位置，向兩邊擴展：O(n)
- 總時間複雜度為 O(n²)
空間複雜度：O(1)
- 只使用了常數個變數來儲存中間結果
- 不需要額外的資料結構
- 總空間複雜度為 O(1)