zlatan的算法笔记6--回溯法解决切割问题分割回文串（力扣131题）_回溯法解决分割回文串

算法笔记

从第一次算法笔记开始，我们就在讨论回溯法，也说明了回溯法可以解决的几类经典的问题，并在之后几天的题目中进行了组合类问题的练习，今天的算法笔记将开始讨论切割这一类比组合更抽象的问题–切割问题，题目为力扣上的第131题，分割回文串，个人感觉这道题有一定难度，需要克服几个难点。

题目描述

不知道有没有人和我一样看见字符串相关的题目就瑟瑟发抖，但也没办法，咬着牙也要克服这种问题，我个人认为碰到这种情况只能一点点积累相应的技巧，慢慢就会好起来的。回到题目，题目很简短，让我们返回给定字符串s所有可能的分割方案。做过几道题的我们就会敏锐的发现两个点，**第一点什么是回文串，如何判断一个串是不是回文串；第二点如何解决分割问题，它和组合有什么共通的地方。**搞清楚后就开始正式解题。

解题过程

在经典三部曲之前，我们先着手于解决两个问题。

**第一个问题–回文：**什么是回文，通俗来讲就是一串数字或者字符串，我正着读反着读是一样的。

先来个例子123是回文吗？答案是否定的。123正着读是123，反着读就是321了，不一样啊。

举个正面例子，aba怎么样，没问题，正反都是aba；那单个数字和字符是不是？肯定是了，不但这些是回文的，连续相同的数字字符照样是回文的，没有任何的问题！那现在就可以看懂输出中的例子了，那么就开始用代码写回文。

题目当中我们用的回文不是返回它的回文数，只需要判断它是不是回文就行了。那么我们写个函数Ishuiwen判断【如果用英文名就更好了，我这里就通俗一下】，类型是bool型只需要是或否的结果就可以了，里面的参数怎么选择，首先字符串是必须要有的，然后我们需要使用双指针来判断，分别表示一头一尾【如果不知道什么是双指针，我以后会做，可能很久以后】。之后看代码部分，我们写一个循环给终止条件，头位置和尾位置相比，然后头往后走，尾往前走，跟相遇问题一样，如果两边撞上了就跳出循环即可，循环里面来一个判断，两边是不是一样，不一样的话就返回false说明不回文，一样就回文，代码如下：

    bool Ishuiwen(string s, int begin, int end) {
        while(begin < end) {
            if(s[begin++] != s[end--]) {
                return false;
            }
        }
        return true;
    }
1
2
3
4
5
6
7
8

第二个问题–切割： 在组合里面我们选择一个数之后，我们会在剩下的内容里再去选择第二个【这里是无重复选取，重复也类似】，一个一个选。在切割里面，切割一个数就变成了一个分开的数和一段区间，跟代码随想录画的下图一样，切完一个从后面的区间里面再切一个出来，周而复始。弄清楚切割，我们直接开始三部曲，直接结合情境，理解更轻松。

三部曲：

1.选择参数： 组合问题里面我们基本上每次都有一个参数startIndex，这里再复习一下，它的作用每次从集合中选取元素，可选择的范围收缩，我们用startIndex调整可选择范围。放到切割问题我们同样需要startIndex，在这里我们把它理解为切割线本身，它的职责就是作为一把刀划出一个值与另一块区间，就跟切菜一样，一片一片切，第一刀第二刀这样理解，最后把一块整菜全切开。除此之外还需要记录路径与结果的两位老朋友path与result，最后添上输入数组s本身就选完了参数。

2.终止条件： 终止条件很好理解，继续拿切菜举例，我们拿到一根火腿肠，一刀一刀切，什么时候结束，当然是最后一刀切到火腿肠屁股后就算结束。这根火腿肠就是输出字符串s的大小即s.size()，我们的刀就是startIndex，如果切完了，就返回结果，即装盘，返回值即可。
另外，在这里可能有人会问为什么不把能不能回文作为终止条件，我的评价是也可以写，不过在这次的代码中，我把这个判断放到了第三步里面。

        if(s.size() == startInedx) {
            result.push_back(path);
            return;
        }
1
2
3
4

3.循环递归回溯： for循环开始，i为startIndex，条件好理解，难点在于if的判断当中。 如果我们之前做的回文判断为是就记录路径，这有两个小难点，第一个小难点是判断函数里面的参数如何选取。第二个小难点是这条路径怎么表示。

对于第一个难点，我们知道回文是一个头尾元素判断，所以就需要头尾参数，第一个参数很简单字符串本身就行，第二个参数为startIndex，第三个参数为i。这两个参数最难理解，我们先考虑切割一次之后，后面的子串是不是就处在【startIndex，i】的区间内，不要被for循环中i = startIndex这一步误导，startIndex作为切割线是不变化的，而i则是一直++的，i每加一个就代表了一个新的子串，二者中间夹的部分正是我们需要判断的范围，如果理解不了，记得去结语处找视频链接大概16分30秒处去看。

对于第二个难点，这条路径如何记录，就要使用string当中substr函数来操作，substr里面有两个参数，前面表示位置，后面表示长度，然后就可以记录这条路径了。

                string ss = s.substr(startInedx, i - startInedx + 1);
                path.push_back(ss);
1
2

判断完之后，满足就记录路径结果，不满足就continue，之后递归，无重复选取所以i + 1，最后回溯，一切恢复原状，至此结束。

代码部分

class Solution {
public:

    vector<string> path;
    vector<vector<string>> result;

    bool Ishuiwen(string s, int begin, int end) {
        while(begin < end) {
            if(s[begin++] != s[end--]) {
                return false;
            }
        }
        return true;
    }

    void backtracking(string s, int startInedx) {
        if(s.size() == startInedx) {
            result.push_back(path);
            return;
        }

        for(int i = startInedx; i < s.size(); i++) {
            if(Ishuiwen(s, startInedx, i) == true) {
                string ss = s.substr(startInedx, i - startInedx + 1);
                path.push_back(ss);
            }else {
                continue;
            }
            backtracking(s, i + 1);
            path.pop_back();
        }
    }

    vector<vector<string>> partition(string s) {
        backtracking(s, 0);
        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
35
36
37
38

结语

光通过文字描述可能容易讲不清楚整道题目，我尽可能以我对题目的理解讲的更通俗易懂一些，如果还是不明白的话，我强烈推荐看完还是很模糊的小伙伴去花时间看一下代码随想录有关于这道题的视频讲解：https://www.bilibili.com/video/BV1c54y1e7k6/?spm_id_from=333.999.0.0分割回文串，希望大家都可以拿下这道题，变得更强。