该用户太懒了,只留下了38行C++代码
class Solution {
public:
vector<vector<bool>> f;
vector<vector<string>> res;
vector<string> path;
void dfs(string& s, int u) {
if(u == s.size()) {
res.push_back(path);
return;
}
for(int i = u; i < s.size(); i ++) {
if(f[u][i]) {
path.push_back(s.substr(u, i - u + 1));
dfs(s, i + 1);
path.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
int n = s.size();
f = vector<vector<bool>>(n, vector<bool>(n));
for(int k = 0; k < n; k ++) {
for(int i = 0; i < n - k; i ++) {
int j = i + k;
if(k == 0) f[i][j] = true;
else if(k == 1) f[i][j] = (s[i] == s[j]);
else f[i][j] = (s[i] == s[j] && f[i + 1][j - 1]);
}
}
dfs(s, 0);
return res;
}
};