LeetCode 5 Longest Palindromic Substring：動態規劃 O(n²) 求最長回文子串

LeetCode 5「最長回文子串」：給定字符串 s (長度 ≤ 1000)，求最長回文子串。本文介紹動態規劃解法：dp[i][j] 表示 s[i..j] 是否為回文，利用狀態轉移避免重複判斷。

動態規劃設計

狀態定義

dp[i][j] = true 當 s[i..j] 是回文，其中 0 ≤ i ≤ j < n。

初始化

• 長度 1：dp[i][i] = true。
• 長度 0（輔助）：dp[i][i-1] = true (方便長度 2 判斷)。
• 其餘 false。

狀態轉移

s[i..j] 是回文 ⇔ s[i] == s[j] 且 s[i+1..j-1] 是回文。
即：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]。

遍歷順序

按子串長度 len = 2..n 遞增，內層遍歷起點 i = 0..n-len，j = i+len-1。
此時 dp[i+1][j-1] (長度 len-2) 已計算。

記錄最長

維護 maxLen 和 start，更新時記錄。

完整代碼（C++）

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n <= 1) return s;

        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int start = 0, maxLen = 1;

        // 長度 1
        for (int i = 0; i < n; ++i) dp[i][i] = true;
        // 長度 0 輔助
        for (int i = 1; i < n; ++i) dp[i][i-1] = true;

        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len <= n; ++i) {
                int j = i + len - 1;
                if (s[i] == s[j] && dp[i+1][j-1]) {
                    dp[i][j] = true;
                    if (len > maxLen) {
                        maxLen = len;
                        start = i;
                    }
                }
            }
        }
        return s.substr(start, maxLen);
    }
};

複雜度

• 時間：O(n²) — 雙重循環遍歷所有子串。
• 空間：O(n²) — 二維 DP 表。可優化至 O(n) (僅保留上一行) 但代碼較繁瑣。

優化：中心擴展法 O(n²) 時間 O(1) 空間

枚舉回文中心（2n-1 個：字符位和字符間隙），向兩側擴展。
代碼更短、空間更優，面試常作為進階解法。

string longestPalindrome(string s) {
    int n = s.size(), start = 0, maxLen = 1;
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < n && s[l] == s[r]) {
            if (r - l + 1 > maxLen) { start = l; maxLen = r - l + 1; }
            --l; ++r;
        }
    };
    for (int i = 0; i < n; ++i) {
        expand(i, i);   // 奇數長度
        expand(i, i+1); // 偶數長度
    }
    return s.substr(start, maxLen);
}

Manacher 算法 O(n) — 線性時間最優解

利用回文對稱性避免重複擴展，線性掃描。代碼較複雜，面試中了解原理即可，通常不要求默寫。

總結

最長回文子串三大解法：

建議掌握中心擴展法作為主力，動態規劃作為理解遞推關係的基礎，Manacher 作為拓展視野。