MediumRating 1581
5. Longest Palindromic Substring
two-pointersstringdynamic-programming
解題說明
Longest Palindromic Substring
題目描述：給定字串 s，找出最長的回文子字串。
解題思路：中心擴展法：對每個位置（以及相鄰兩位置之間），向外擴展以找到最長回文。奇數長度（單字元中心）和偶數長度（雙字元中心）需分別處理。每次擴展時間 O(n)，共 2n-1 個中心，總時間 O(n²)，空間 O(1)。
C++ 解法
複雜度分析
時間複雜度：O(n²) — 每個中心最多擴展 n 步，共 O(n) 個中心。
空間複雜度：O(1) — 只用常數個變數。
虛擬碼
1. For each center i (and gap between i and i+1): a. Expand outward while chars match b. Record length and starting index 2. Return longest palindrome found
其他解法
DP O(n²) 時間，O(n²) 空間：維護 dp[i][j] 表示 [i,j] 是否為迴文 — 空間複雜度更差。
中心擴展固定端點 O(n³)：對各端點配對嘗試擴展，逐一檢查 — 時間複雜度更差。
延伸思考
- 若要所有最長迴文子串？
- 若數據流式到達？
- 如何在 O(n) 時間內求解（如 Manacher 演算法）？