class Solution {
public:
std::vector<std::vector<std::string>> res;
std::vector<std::string> path;
bool check(const std::string &s, int start, int end){
for (int i = start, j = end; i < j; i++, j--){
if (s[i] != s[j]) return false;
}
return true;
}
// 只有 start=0 和上面才等价 反例 start=5 s[5]和s[end-5] 应为 s[5]和s[end-1]
// bool check(const std::string &s, int start, int end){
// for (int i = start; i < end/2; i++){
// if (s[i] != s[end - i]) return false;
// }
// return true;
// }
// 错误 int& startIndex 为非常量左值引用 无法和backtracking(s, i + 1);里的右值i+1绑定
// 此处由于递归函数的特殊性 参数startIndex的类型要使用非引用类型
void backtracking(const std::string& s, int startIndex){
if (startIndex >= s.size()){
res.push_back(path);
return;
}
for (int i = startIndex; i < s.size(); i++){
if (check(s, startIndex, i)){
std::string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
}
// 错误 总是遗漏continue
else continue;
backtracking(s, i + 1);
path.pop_back();
}
}
vector<vector<string>> partition(std::string s) {
backtracking(s, 0);
return res;
}
};