Day132 | 灵神 | 回溯算法 | 子集型 分割回文子串

131.分割回文子串

131. 分割回文串 - 力扣（LeetCode）

思路：

其实就和子集一样的，每次加入一个字符然后判断是不是回文串，是的话加入答案集合不是的话就不加入答案

笔者写过很多次这道题了，不想写题解了，大家看灵神讲解吧

回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili

完整代码：

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
35
36
class Solution {
public:
    vector<vector<string>> res;
    bool is(string s,int begin,int end)
    {
        for(int i=begin,j=end;i<j;i++,j--)
        {
            if(s[i]!=s[j])
                return false;
        }
        return true;
    }
    void backtracking(string s,vector<string> path,int index)
    {
        if(index==s.size())
        {
            res.push_back(path);
            return;
        }
        for(int i=index;i<s.size();i++)
        {
            if(is(s,index,i))
            {
                path.push_back(string(s.begin()+index,s.begin()+i+1));
                backtracking(s,path,i+1);
                path.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        vector<string> path;
        backtracking(s,path,0);
        return res;
    }   
};