LeetCode Palindrome Partitioning I & II：DFS 全部分割與 DP 最少切分

LeetCode Palindrome Partitioning I & II：回文分割問題完整解析

Problem I：輸出所有回文分割方案

方法一：DFS 回溯（指數複雜度）

vector> partition(string s) {
    vector> res;
    vector path;
    dfs(s, 0, path, res);
    return res;
}
void dfs(string& s, int start, vector& path, vector>& res) {
    if (start == s.size()) { res.push_back(path); return; }
    for (int len = 1; start + len <= s.size(); len++) {
        if (isPalindrome(s, start, start + len - 1)) {
            path.push_back(s.substr(start, len));
            dfs(s, start + len, path, res);
            path.pop_back();
        }
    }
}
bool isPalindrome(string& s, int l, int r) {
    while (l < r) if (s[l++] != s[r--]) return false;
    return true;
}

時間 O(2ⁿ)，空間 O(n)。

方法二：DP 自底向上構建所有方案（同樣指數但無遞歸開銷）

res[i] 存儲 s[0..i-1] 的所有分割。預計算 isPal[j][i] 表示 s[j..i] 是否回文：

vector> partition(string s) {
    int n = s.size();
    vector>> res(n + 1);
    res[0].push_back({});
    vector> isPal(n, vector(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (s[i] == s[j] && (i - j <= 1 || isPal[j+1][i-1])) {
                isPal[j][i] = true;
                for (auto& prev : res[j]) {
                    auto cur = prev;
                    cur.push_back(s.substr(j, i - j + 1));
                    res[i+1].push_back(cur);
                }
            }
        }
    }
    return res[n];
}

Problem II：求最少切分次數

方法一：DP + 預計算回文表 O(n²)

int minCut(string s) {
    int n = s.size();
    vector cut(n + 1, INT_MAX);
    vector> isPal(n, vector(n));
    cut[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (s[i] == s[j] && (i - j <= 1 || isPal[j+1][i-1])) {
                isPal[j][i] = true;
                cut[i+1] = min(cut[i+1], cut[j] + 1);
            }
        }
    }
    return cut[n] - 1;  // 切分數 = 塊數 - 1
}

方法二：中心擴展法 O(n²) 時間、O(n) 空間（無需 isPal 表）

對每個中心 i 向兩側擴展奇/偶長度回文，直接更新 cut：

int minCut(string s) {
    int n = s.size();
    vector cut(n + 1);
    for (int i = 0; i <= n; i++) cut[i] = i - 1;  // 最壞情況：每字符獨立
    for (int i = 0; i < n; i++) {
        // 奇長度：中心 i
        for (int j = 0; i-j >= 0 && i+j < n && s[i-j] == s[i+j]; j++)
            cut[i+j+1] = min(cut[i+j+1], 1 + cut[i-j]);
        // 偶長度：中心 i, i+1
        for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1] == s[i+j]; j++)
            cut[i+j+1] = min(cut[i+j+1], 1 + cut[i-j+1]);
    }
    return cut[n];
}

核心區別總結