DAY 7 試題

問題描述

給定一個字串 s，請返回字串中回文子字串的數量。回文是指從前往後和從後往前讀取結果相同的字串，而子字串是字串中的連續字符序列。

範例 1：

• 輸入: s = "abc"
• 輸出: 3
• 解釋: 三個回文子字串分別為 "a"、"b"、"c"。

範例 2：

• 輸入: s = "aaa"
• 輸出: 6
• 解釋: 六個回文子字串為 "a"、"a"、"a"、"aa"、"aa"、"aaa"。

限制：

• 1 <= s.length <= 1000
• s 只包含小寫英文字符。

解題思路

這個問題的核心是找到所有的回文子字串，並計算它們的數量。可以使用之前在第四天練習時提到的中心擴展法來解決這個問題。對於每一個可能的中心，從該中心向外擴展來檢查是否是回文，這樣可以在 O(n^2) 的時間內解決問題。

具體方法如下：

1. 中心擴展法：對於每一個字符和每一對相鄰字符作為中心，嘗試從中心向兩邊擴展，檢查是否形成回文。
2. 處理奇數長度與偶數長度的回文：中心擴展時，既需要考慮單個字符作為中心（處理奇數長度的回文），也要考慮兩個相鄰字符作為中心（處理偶數長度的回文）。

class Solution {
public:
    int countSubstrings(string s) {
        int count = 0;  // 計算回文子字串的數量
        int n = s.size();

        // 中心擴展法
        for (int i = 0; i < n; i++) {
            // 以單個字符為中心（處理奇數長度的回文）
            count += expandAroundCenter(s, i, i);
            // 以兩個相鄰字符為中心（處理偶數長度的回文）
            count += expandAroundCenter(s, i, i + 1);
        }

        return count;
    }

    // 擴展中心，並計算回文子字串的數量
    int expandAroundCenter(const string& s, int left, int right) {
        int count = 0;

        // 當兩邊字符相等時，繼續擴展
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            count++;  // 找到一個回文子字串
            left--;  // 向左擴展
            right++; // 向右擴展
        }

        return count;
    }
};

解法重點與分析

countSubstrings 函數：

• 初始化回文子字串計數 count 為 0。
• 使用中心擴展法，對每個字符進行兩次擴展：一次擴展處理奇數長度的回文（單個字符為中心），一次處理偶數長度的回文（兩個相鄰字符為中心）。
• 將每次擴展找到的回文子字串數量累加到 count 中。

expandAroundCenter 函數：

• 從給定的 left 和 right 開始，當 left 和 right 位置的字符相同時，進行擴展並計算回文子字串數量。
• 每次擴展後，left 向左移動，right 向右移動，直到不能形成回文為止。

本題重點

這題的關鍵點在於如何有效率地找到所有的回文子字串。使用中心擴展法是一種簡單且高效的解法，因為每個字符都可以作為中心點進行回文檢查。這個方法的時間複雜度為 O(n^2)，其中 n 是字串的長度，能夠在合理的時間內處理最大長度為 1000 的字串。

總結

透過中心擴展法，我們能夠有效地解決這類回文子字串的計數問題。此方法不僅適用於回文的查找，還能處理不同長度的回文情況，並且在不需要額外的記憶體空間的情況下，提供了高效的解法。這樣的技巧也可以應用到其他需要查找子字串或子序列的問題中。

以上是第七天的自學內容分享，謝謝大家。