链接：131. 分割回文串
class Solution {
public:
// 判断从字符串s，[begin, i]的字符串是否为回文串
bool is_same(const std::string& s, int begin, int i) {
while(begin <= i) {
if(s[begin] != s[i]) {
return false;
}
++begin;
--i;
}
return true;
}
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
if(s.size() == 0) {
return res;
}
int begin = 0; // 截取字符串的开头
vector<string> path; // 临时路径
dfs(s, begin, path, res);
return res;
}
void dfs(const std::string& s, int begin, vector<string>& path, vector<vector<string>>& res) {
if(begin >= s.size()) {
res.push_back(path);
return;
}
for(int i = begin; i < s.size(); ++i) {
// 判断当前层字符串[begin,i]是否为回文串
if(!is_same(s, begin, i)) {
continue;
}
// s[begin,i]为回文串
path.push_back(s.substr(begin, i-begin+1));
// 递归下一层
dfs(s, i+1, path, res);
// 回溯
path.pop_back();
}
}
};