131. 分割回文串

难度：🟡 Medium | 标签：回溯、动归 | 状态：⬜ LeetCode 链接

思路

回溯枚举切割点。对每个候选子串先判回文，是再 DFS 下去。 可用 DP 预处理 pal[i][j] 加速 O(1) 判断。

代码

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

复杂度

• 时间 O(n · 2ⁿ)，空间 O(n)

易错 / 回顾

• 不回文直接 continue，剪枝大量分支
• DP 预处理回文表能让 isPal O(1)，长字符串值得做
• substr(start, len)：第二个参数是长度，不是结束下标