回溯算法-分割问题-分割回文串_c++回溯法:分割回文子字符串

leetcode131.分割回文串

class Solution {
private:
    vector<string> path;
    vector<vector<string>> result;
    void backtracking(int startIndex,string s){//1.确定函数的参数和返回值
        //2.确定递归的终止条件，并添加结果
        if(startIndex>=s.size()){
            result.push_back(path);
            return ;
        }
        //3.确定单层的循环逻辑
        for(int i=startIndex;i<s.size();i++){
            if(isPalindrome(s,startIndex,i)){//处理节点
                path.push_back(s.substr(startIndex,i-startIndex+1));
            }else{
                continue;
            }
            backtracking(i+1,s);//递归
            path.pop_back();//回溯
        }
    }
    //判断是不是回文子串
    bool isPalindrome(const string& s,int startIndex,int endIndex){
        for(int i=startIndex,j=endIndex;i<j;i++,j--){
            if (s[i]!=s[j]) return false;
        }
        return true;
    }
public:
    vector<vector<string>> partition(string s) {  
        backtracking(0,s);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

注意点：

1. 在回溯算法三部曲的第二步中记得收集结果集，本题的结果均是在叶子结点收集的。并且本题对result结果没有要求，要求在path收集的时候已经判断过了，这里只要判断startIndex是否到头了就行。
2. 在回溯算法三部曲的第三步单层逻辑中，调用isPalindrom判断是否是回文串，如果一旦有一个不是回文串了记得continue继续留在本层向后遍历，就不要到递归到下一层去了，因为题目要求的是所有子串均为回文子串，否则会有RunTimeError vector容器会爆内存（vector会不断扩容），并且这也不符合题意不是么。
3. path.push_back(s.substr(startIndex,i-startIndex+1));c++ substr方法定义是 截取startIndex包括start以后的多少个字符，明显从s[startIndex]到s[i]有i-startIndex+1个字符；