我在做Leetecode的一道题时，遇到了一道切割字符串求解回文字符串的题目，题目大意如下:
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
["aa","b"],
["a","a","b"]
]
这个时候我们需要使用DFS算法，进行深搜，但是这个里我们需要注意的一个问题是，每个字符只能用一次，而且不能使用拼接的方式，需要直接从string s中截取子字符串，所以我们使用s.substr(start,count)的方式。这个不同于之前的combinationSum的题目，需要有一个中间target保存。我们只需要传入下面几个参数即可，使用step来标示当前指向s的开头index，i为结束index。
void DFS(string &s,vector<vector<string>> &result,vector<string> &path,int step){
if(step>=s.size()){
result.push_back(path);
return;
}
for(auto i = step;i<s.size();i++){
if(is_palindrome(s,step,i)){
path.push_back(s.substr(step,i-step+1));
DFS(s,result,path,i+1);
path.pop_back();
}
}
}
bool is_palindrome(string &s,int start,int end){
while(start < end){
if(s[start]!=s[end])
return false;
start++;
end--;
}
return true;
}
};
一个长度为n 的字符串，有n-1 个地方可以砍断，每个地方可断可不断，因此复杂度为O(2^(n-1))
