给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

**输入：**s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2：

**输入：**s = “a”
输出：[[“a”]]

提示：

1 <= s.length <= 16

s 仅由小写英文字母组成

按字符进行拼接，每个字符有两个选择

与前一个字符相拼

若已拼字符为回文串，则当前字符可作为新串的开头

可以提前获取每段是否为回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    vector<vector<string>> ans;
    vector<string> mid;
    vector<vector<string>> partition(string s) {
        vector<vector<bool>> flag(s.size() + 1, vector<bool>(s.size() + 1));
        for (int i = 0; i < s.size(); i++) {
            flag[i][i + 1] = true;
            flag[i][i] = true;
        }
        isVaild(s, flag);
        dfs(s, 0, 1, flag);
        return ans;
    }
    void dfs(string &s, int i, int j, vector<vector<bool>> &flag) {
        if (s.size() == j) {
            if (flag[i][j]) {
                mid.push_back(s.substr(i, j - i));
                ans.push_back(mid);
                mid.pop_back();
            }
            return;
        }

        if (flag[i][j]) {
            mid.push_back(s.substr(i, j - i));
            dfs(s, j, j + 1, flag);
            mid.pop_back();
        }
        dfs(s, i, j + 1, flag);
    }
    void isVaild(string &s, vector<vector<bool>> &flag) {
        int n = s.size();
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 2; j <= n; j++) {
                flag[i][j] = (s[i] == s[j - 1]) && flag[i + 1][j - 1];
            }
        }
    }
};