Day66 代码随想录打卡|回溯算法篇---分割回文串

题目（leecode T131）：

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。

方法：本题是一个分割回文串的问题，是回溯算法的另一类问题。 针对一个字符串，我们要对其进行分割，并且确保分割后生成的子串也必须全都是回文串。分析回溯三部曲

1：传入参数与返回值：传入字符串s，以及切割的起始位置startIndex，不需要返回值

2：终止条件：因为切割位置startIndex控制的是切割的起始位置，当startIndex大于等于s.size时，就意味着已经切到了最后，也就该停止了。

3：单层处理逻辑：在单层中我们需要从字符串中截取子串。

在for (int i = startIndex; i < s.size(); i++)循环中，我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。

首先判断这个子串是不是回文，如果是回文，就加入在vector<string> path中，path用来记录切割过的回文子串。

题解：
 

class Solution {
private:
    vector<string> path;
    vector<vector<string>> result;
    void backtracking(const string& s,int startIndex){
        if(startIndex >= s.size()){             //终止条件
            result.push_back(path);
            return;
        }
        for(int i = startIndex; i < s.size(); i++){
            if(isPalindrome(s, startIndex, i)){
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
            }else{
                continue;
            }
            backtracking(s, i + 1); // 寻找i+1为起始位置的子串
            path.pop_back(); // 回溯过程，弹出本次已经添加的子串
        }
    }
    bool isPalindrome(const 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;
    }
public:
    vector<vector<string>> partition(string s) {
        result.clear();
        path.clear();
        backtracking(s, 0);
        return result;
    }
};