给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。
返回s所有可能的回文串分割方案。
class Solution {
public:
/**
* @param s: A string
* @return: A list of lists of string
*/
void helper(vector<vector<string> > & ret, string s, vector<string> tmp) {
if(s.size() == 0) {
ret.push_back(tmp);
return;
}
for(int i = 1; i <= s.size(); ++i) {
string str = s.substr(0, i);
//cout << str << endl;
if(check(str)) {
tmp.push_back(str);
helper(ret, s.substr(i), tmp);
tmp.pop_back();
}
}
}
bool check(string str) {
if(str.size() == 0 || str.size() == 1) {
return true;
}
int len = str.size();
for(int i = 0; i <= len/2 - 1; ++i ) {
if(str[i] != str[len-1-i]) {
return false;
}
}
return true;
}
vector<vector<string>> partition(string s) {
// write your code here
vector<vector<string> > ret;
vector<string> tmp;
helper(ret, s, tmp);
return ret;
}
};
