DAY 4 試題

問題描述

給定一個字串 s，要求返回該字串中的最長回文子字串。回文指的是正著讀和反著讀都相同的字串。

範例：
Input: s = "babad"
Output: "bab"
Explanation: "aba" 也是一個正確答案，因為它也是回文。

Input: s = "cbbd"
Output: "bb"

限制條件：

• 1 <= s.length <= 1000
• 字串 s 僅包含數字和英文字母。

解題思路

這道題的關鍵在於如何有效地找到字串中的最長回文子字串。暴力解法可以遍歷所有的子字串並檢查是否為回文，但這樣的解法效率太低，時間複雜度為 O(n³)，不適合處理長度為 1000 的字串。

我們可以使用中心擴展法來提高效率。對於每個字符，將它作為回文的中心，從這裡向外擴展，檢查其周圍的字符是否對稱。對於偶數長度的回文，需要同時從兩個相鄰的字符開始擴展。

核心步驟：

1. 中心擴展：每個字符都可能是回文的中心。分兩種情況：

• 奇數長度的回文：以單個字符作為中心，向左右擴展。
• 偶數長度的回文：以相鄰的兩個字符作為中心，向左右擴展。

2. 記錄最長回文子字串：每次找到回文時，記錄當前回文子字串的長度，並保持更新最長的回文子字串。

3. 時間複雜度：該方法對每個字符進行兩次擴展（奇數和偶數），每次擴展最多需要 O(n) 的時間，因此總體時間複雜度為 O(n²)。

class Solution {
public:
    // 擴展回文的輔助函數，返回當前擴展得到的回文子字串
    string expandAroundCenter(const string &s, int left, int right) {
        // 向兩邊擴展，直到左右兩邊的字符不再相同
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            left--;
            right++;
        }
        // 返回當前找到的回文子字串
        return s.substr(left + 1, right - left - 1);
    }

    // 返回字串中的最長回文子字串
    string longestPalindrome(string s) {
        if (s.empty()) return "";  // 如果字串為空，返回空字串

        string longest = "";  // 用於存儲最長回文子字串
        for (int i = 0; i < s.length(); i++) {
            // 針對奇數長度回文，擴展回文
            string oddPalindrome = expandAroundCenter(s, i, i);
            if (oddPalindrome.length() > longest.length()) {
                longest = oddPalindrome;
            }

            // 針對偶數長度回文，擴展回文
            string evenPalindrome = expandAroundCenter(s, i, i + 1);
            if (evenPalindrome.length() > longest.length()) {
                longest = evenPalindrome;
            }
        }
        return longest;
    }
};

解法重點與分析

中心擴展法：

• 每個字符（或字符之間的空隙）都被當作回文的中心，從這裡向左右擴展。
• 這種方法避免了檢查所有子字串，因此比暴力解法更加高效。

時間複雜度：O(n²)

• 對每個字符進行兩次擴展（針對奇數和偶數回文），每次擴展最多需要 O(n) 的時間，因此總體時間複雜度為 O(n²)。

空間複雜度：O(1)

• 只使用了常數空間來記錄變量，沒有額外的數據結構。

總結

在這道題中，使用中心擴展法有效地解決了最長回文子字串的問題。它的核心思路是將每個字符或相鄰字符當作回文的中心，從該位置向兩邊擴展，並不斷更新當前找到的最長回文子字串。這種方法的優勢在於它避免了暴力解法中逐一檢查所有子字串的低效操作，將時間複雜度從 O(n³) 降低到了 O(n²)，是一種相對高效且容易實現的解法。

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