题目描述

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

样例

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

算法1

(DFS枚举) $O(2^n)$

枚举所有方案，所以直接用DFS求解；
题目中需要判断是否为回文串，可以事先通过$O(n^2)$的DP预处理好；
然后枚举$n - 1$个空哪些需要断开即可。

时间复杂度

长为$n$的字符串，有$n - 1$个空，每个空都有断开或者不断开两种选择，所以$O(2^n)$。

参考文献

C++ 代码

class Solution {
public:
    vector<vector<string>> partition(string s) {
        if (s.empty()) return {};
        int n = s.size();
        vector<vector<bool>> f(n + 1, vector<bool>(n + 1));
        f[0][0] = true;
        for (int i = n; i >= 1; --i){
            for (int j = i; j <= n; ++j){
                f[i][j] = s[i - 1] == s[j - 1] && (j - i < 2 || f[i + 1][j - 1]);
            }
        }

        vector<string> path;
        vector<vector<string>> res;
        dfs(path, res, 0, s, f);
        return res;
    }

    void dfs(vector<string> &path, vector<vector<string>> &res, int idx, string &s, const vector<vector<bool>> &f){
        if (idx >= s.size()){
            res.push_back(path);
            return;
        }

        for (int len = 1; idx + len - 1 < s.size(); ++len){
            if (f[idx + 1][idx + len]){
                string sub = s.substr(idx, len);
                path.push_back(sub);
                dfs(path, res, idx + len, s, f);
                path.pop_back();
            }
        }
    }
};