题目描述
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
题解
分两步。第一步对s使用dp方法确定回文子串。第二步使用回溯法进行分割。
第一步，dp[i][j]代表s(i,j)是否为回文（包含i和j）字符串，注意当ij之间的字符大于等于3个时，dp[i][j]=dp[i+1][j-1]&&s[i]\==s[j]，即i递减，j递增，又j>=i，即可确定i，j的递推方向。第二步，dfs(ps)，将对dp[ps][i] (ps<=i<n)中为true的，s(ps,i)放入组合，进行dfs，当ps==n时，当前组合放入结果。注意dfs的优化，模版类使用传址，复用变量（如字符串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
41
42
| int len; bool **dp;
void dfsHelper(string& s,int ps, vector<string>& tmp, vector<vector<string>>& res)
{
if (ps >=len)
{
res.push_back(tmp);
return;
}
for (int i = ps; i < len; i++)
{
if (dp[ps][i])
{
tmp.push_back(s.substr(ps, i - ps + 1));
dfsHelper(s, i+1, tmp, res);
tmp.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
len = s.length();
dp =new bool*[len];
for (int i = 0; i < len; i++)
dp[i] = new bool[len];
for (int i = 0; i < len; i++)
for (int j = 0; j < len; j++)
dp[i][j] = 0;
for (int i = 0; i < len; i++)
dp[i][i] = 1;
for (int i = 1; i < len; i++)
dp[i][i - 1] = 1;
for (int i = 1; i < len; i++)
{
for (int j = 0; j < len - i; j++)
{
dp[j][j + i] = dp[j + 1][j + i - 1] && (s[j] == s[j + i]);
}
}
vector<string> tmp = {};
vector<vector<string>> res;
dfsHelper(s, 0, tmp, res);
return res;
}
|