題目描述:給定字串 s,計算其中有多少個回文子字串(包含單個字元)。
解題思路:中心擴展法:對每個中心(奇數長度的單字元中心和偶數長度的雙字元中心),向外擴展計算以此為中心的回文數量。每成功擴展一次就計數加一。共 2n-1 個中心,每個中心最多擴展 n 次,總時間 O(n²)。
時間複雜度:O(n²) — 2n-1 個中心,每個最多擴展 n 步。
空間複雜度:O(1) — 只用常數個變數。
1. count = 0
2. For each center in [0, 2n-2]:
a. l = center/2, r = l + center%2
b. While s[l] == s[r] and in bounds:
count++; l--; r++
3. Return countDP O(n²) 時間,O(n²) 空間:維護 dp[i][j] 計數迴文子串 — 空間複雜度更差。
中心擴展逐一檢查 O(n³):對各中心擴展,逐一驗證 — 時間複雜度更差。