LeetCode 5. 最長回文子串：中心擴展法 O(n²) 時 O(1) 空間完美解法

LeetCode 5. 最長回文子串：中心擴展法 O(n²) 時 O(1) 空間完美解法

題目：給定字符串 S（長度 ≤ 1000），找出最長回文子串，保證唯一解。
難度：Medium
核心思路：回文中心對稱特性 → 枚舉所有可能中心 → 向兩側擴展 → 記錄最長。

算法設計精要

1. 兩類中心情況

• 單中心（奇數長度）：如 "aba"，中心為字符 'b'
• 雙中心（偶數長度）：如 "abba"，中心為 'b'|'b' 間隙

遍歷每個字符位置 i，同時檢查 (i, i) 與 (i, i+1) 兩種中心。

2. 提前終止優化

當遍歷至後半段，理論最大可能長度 2 * (n - 1 - i) + 1 < 當前最長長度時，直接 break，減少無效循環。

3. 邊界處理

• 使用 char[] 而非 String.split("")，避免首位空串且 O(1) 訪問
• 擴展循環條件 left >= 0 && right < len 防越界

完整 Java 實現（含詳細註釋）

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s;
        char[] arr = s.toCharArray();
        int n = arr.length;
        int maxLen = 0, start = 0;

        for (int i = 0; i < n; i++) {
            // 提前終止：剩餘字符即使全對稱也超不過當前最長
            if (i > (n - 1) / 2 && 2 * (n - 1 - i) + 1 < maxLen) break;

            int len1 = expand(arr, i, i);     // 單中心
            int len2 = expand(arr, i, i + 1); // 雙中心

            if (len1 > maxLen || len2 > maxLen) {
                if (len1 > len2) {
                    maxLen = len1;
                    start = i - (len1 - 1) / 2;
                } else {
                    maxLen = len2;
                    start = i + 1 - len2 / 2;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }

    // 從 (l, r) 向兩側擴展，返回回文長度
    private int expand(char[] arr, int l, int r) {
        while (l >= 0 && r < arr.length && arr[l] == arr[r]) {
            l--; r++;
        }
        return r - l - 1; // 退出時多擴展一步，需減 1
    }
}

複雜度分析

進階對比：Manacher 算法 O(n)

利用回文對稱性復用已計算信息，線性時間求解。代碼較複雜，面試中中心擴展法通常足夠，但理解 Manacher 核心思想（維護最右邊界 R、中心 C、鏡像位置）是進階必修課。

測試用例驗證

@Test
public void test() {
    Solution sol = new Solution();
    assertEquals("cbaabc", sol.longestPalindrome("cabcbaabcaa"));
    assertEquals("a", sol.longestPalindrome("a"));
    assertEquals("bb", sol.longestPalindrome("bb"));
    assertEquals("aba", sol.longestPalindrome("babad")); // 或 "bab"
    assertEquals("ccc", sol.longestPalindrome("ccc"));
}

避坑指南

• ❌ 用 String.split("") 產生 String[] → 首元素為空串、內存開銷大、訪問慢
• ❌ 忽略雙中心情況 → 漏掉偶數長度回文
• ❌ 邊界條件寫錯 → ArrayIndexOutOfBoundsException
• ✅ 用 char[] + 雙指針擴展 + 提前終止 = 簡潔高效

「中心擴展法是回文類問題的通用模板：枚舉中心 → 擴展驗證 → 更新答案。掌握它，LeetCode 647、516 等題迎刃而解。」