题目链接
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串是正着读和反着读都一样的字符串。
示例 1：
1
2
| 输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
|
示例 2：
暴力所有分隔符，显然对一个长为 $n$ 的字符串最多可以划分成 $n$ 个子串，那么我们就可以暴力所有的可能，复杂度 $O(2^n)$~
注意最后一个位置必须要切，拿样例 1 举例：
1
2
3
4
5
| aab
1: aab|
2: ab|b|
3: a|ab|
4: a|a|b|
|
还有一个细节，因为位数固定了，但是小数的二进制位数比大数小，所以小数的二进制数要在前面补 0，AC代码如下：
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
| class Solution {
public:
bool check(string s) {
string ss = s;
reverse(s.begin(), s.end());
return s == ss;
}
vector<vector<string>> partition(string s) {
int n = s.size();
if (n == 1) return {{s}};
else {
vector<vector<string>> ans;
for (int i = 0; i < (1 << (n - 1)); i++) {
int pos = 0, flag = 1;
vector<string> v;
string div = "";
int num = i;
while (num) {
div = to_string(num % 2) + div;
num /= 2;
}
while (div.size() < n - 1) div = '0' + div;
div += '1';
for (int j = 0; j < n; j++) {
if (div[j] == '1') {
string ss = s.substr(pos, j - pos + 1);
v.emplace_back(ss);
if (!check(ss)) flag = 0;
pos = j + 1;
}
}
if (flag) ans.emplace_back(v);
}
return ans;
}
}
};
|