Leetcode131: 分割回文字符串

【题目描述】
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

【思路】
使用回溯法
全局使用一个path
每次分割出一段字符，判断分割的的子字符串是否为回文，若为回文加入path，对剩下的继续进行。若不是回文则剪枝。
回溯结束的条件：字符串为空（全部已经分割）

vector<vector<string>> partition(string s) {
    //Leetcode131: 分割回文串
    vector<vector<string>> res;
    vector<string> path;
    if (s.size() == 0) return res;
    helpPar(s, res, path, 0);
    return res;

}
void helpPar(string s, vector<vector<string>>& res, vector<string>& path, int start) {
    //cout << "start: " << start << endl;
    //cout << "path: ";
    if (start >= s.size()) {
        res.push_back(path);
        return;
    }
    else {
        for (int i = start; i <s.size(); i++) {
            if (isPal(s, start, i)) {
                //cout << "pal start: " << start << endl;
                //cout << "pal end: " << i << endl;
                //cout << "isPal: " << s.substr(i, i - start + 1) << endl;;
                path.push_back(s.substr(start,i-start+1));
                helpPar(s, res, path, i+1);
                path.pop_back();
            }
        }
    }
}

bool isPal(string s, int start, int end) {
    if (start > end) return true;
    if (s[start] != s[end]) return false;
    if (s[start] == s[end]) return isPal(s, start + 1, end - 1);
}