LeetCode 131 分割回文串：DFS 回溯算法深度解析

題目描述

給定字符串 s，將其分割成若干子串，使每個子串均為回文。返回所有可能的分割方案。

示例：s = "aab" → [["aa","b"], ["a","a","b"]]

核心思路：深度優先搜索 + 回溯

將字符串視為在字符間放置「分割板」。從左向右遞歸嘗試在每個位置放或不放分割板，約束條件：每段必須是回文。

算法流程

1. 遞歸函數 dfs(s, path, result, prev, start)：
   prev：當前段起始索引；
   start：下一個待檢查的分割位置（字符間隙）。
2. 終止條件：start == s.size()，檢查最後一段 [prev, end] 是否回文，是則加入結果集。
3. 遞歸分支：
   不分割：dfs(prev, start+1)；
   分割：若 [prev, start-1] 是回文，則 path.push_back(substr)，遞歸 dfs(start, start+1)，回溯彈出。

C++ 參考實現

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> path;
        dfs(s, path, result, 0, 1);
        return result;
    }

private:
    void dfs(const string& s, vector<string>& path,
             vector<vector<string>>& result, int prev, int start) {
        if (start == s.size()) {
            if (isPalindrome(s, prev, start - 1)) {
                path.push_back(s.substr(prev, start - prev));
                result.push_back(path);
                path.pop_back();
            }
            return;
        }
        // 不分割
        dfs(s, path, result, prev, start + 1);
        // 分割
        if (isPalindrome(s, prev, start - 1)) {
            path.push_back(s.substr(prev, start - prev));
            dfs(s, path, result, start, start + 1);
            path.pop_back();
        }
    }

    bool isPalindrome(const string& s, int l, int r) {
        while (l < r && s[l] == s[r]) { ++l; --r; }
        return l >= r;
    }
};

複雜度分析

• 時間：O(n × 2ⁿ)，最壞情況（全同字符）每個間隙可分可不分，共 2ⁿ⁻¹ 種分法，每種驗證 O(n)。
• 空間：O(n) 遞歸棧 + O(n) 路徑存儲，輸出空間不計入。

優化方向

• 預處理 isPal[i][j] 表，O(1) 判斷回文，避免重複掃描。
• 動態規劃 + 回溯結合，先生成所有回文子串圖再 DFS。