LeetCode 5. 最長回文子串：從暴力到中心擴展法 O(n²)時間 O(1)空間

題目描述

給定字符串 S（長度 ≤ 1000），找出最長回文子串。假設唯一解。

三種解法演進

1. 暴力枚舉 O(n³)

枚舉所有子串長度（從長到短）、起始位置，判斷是否回文。超時。

2. 動態規劃 O(n²)時間 O(n²)空間

dp[i][j] 表示 s[i..j] 是否回文。狀態轉移：dp[i][j] = (s[i]==s[j]) && dp[i+1][j-1]。空間超限（Memory Limit Exceeded）。

3. 中心擴展法 O(n²)時間 O(1)空間 ⭐ 推薦

回文中心有 2n-1 種可能（n 個字符中心 + n-1 個間隙中心）。對每個中心向兩側擴展，記錄最長。

中心擴展法完整實現

 longest.length()) longest = p1;
            String p2 = expand(s, i, i + 1); // 偶數長，中心在間隙
            if (p2.length() > longest.length()) longest = p2;
        }
        return longest;
    }

    private String expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--; r++;
        }
        return s.substring(l + 1, r);  // 回文實際範圍 [l+1, r-1]
    }
}

C++ 版本

= 0 && r < s.size() && s[l] == s[r]) { l--; r++; }
        int len = r - l - 1;
        if (len > bestLen) { bestLen = len; bestL = l + 1; }
    };
    for (int i = 0; i < s.size(); ++i) {
        expand(i, i);
        expand(i, i + 1);
    }
    return s.substr(bestL, bestLen);
}

複雜度對比

工程建議

• 面試/競賽首選中心擴展法：代碼簡短、空間優、易正確。
• 極長字符串（>10⁵）需 Manacher 算法。
• 注意空串、單字符邊界情況。