题目
思路
从i开始搜索所有子串，如果[i..j]是回文子串则添加到答案数组中，然后用j 1当做新的i开启下一次搜索。回溯时再把添加的子串弹出去。当i == n时就是一个正确的分割方案。
如果不打表每次判断子串是不是回文都会浪费时间，所以可以用动态规划判断所有子串。 设f(i,j)表示子串[i..j]是否为回文子串： true, i >= j f(i 1, j - 1) && s[i] == s[j], i< j (s[i] == s[j]表示子字符串的首尾字符相同)
代码语言：javascript复制class Solution {
public:
vector<vector<int>> f;
vector<vector<string>> res;
vector<string> ans;
int n;
void dfs(const string& s, int i) {
if (i == n) {
res.push_back(ans);
return;
}
for (int j = i; j < n; j ) {
if (f[i][j]) {
ans.push_back(s.substr(i, j 1 - i));
dfs(s, j 1);
ans.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
n = s.size();
f.assign(n, vector<int>(n, true));
for (int i = n - 1; i >= 0; i--) {
for (int j = i 1; j < n; j ) {
f[i][j] = (s[i] == s[j]) && f[i 1][j - 1];
}
}
dfs(s, 0);
return res;
}
};
