【蓝桥杯速成】| 10.回溯切割

前面两篇内容我们都是在做有关回溯问题的组合应用

今天的题目主题是：回溯法在切割问题的应用

题目一：分割回文串

问题描述

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

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

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

解题步骤

在做这题之前我们需要明确回文串是什么东西👇

那么我们解决这个问题就可以分为分割字符串和判断回文串两个part

运用回溯法分割字符串其实和组合问题是类似的思路

我们需要按照字符串顺序，在所有可能位置砍上一刀，形成不同的字符串碎片

那么为了不错过任何一种可能，就需要按顺序遍历

下面就来尝试使用回溯三部曲！

1.确定函数返回值及参数

依旧使用backtracking这个名字，没有返回值的要求，参数呢传入我们需要使用的字符串s以及一个开始索引startindex即可

这个开始索引是不断变大的，意味着每次砍第一刀下去，第一个碎片的长度在慢慢变大，这也是我们有序分割的重要环节

void backtracking(string s,int startindex)

2.确定终止条件

按照最简单的思路，和之前的组合问题一样，我们会在叶子结点取到该过程的一个答案，再做个对应题目限制的判断，合适就加入result中， 

那么我们的分割也是这样，在叶子节点结束分割，把整个字符串剁碎了，

但需要注意的是，在叶子节点我们得到的不是碎片，而是虽然碎了但仍旧可以拼成完整s的组合体

就像你买了一只烤鸭，咔咔剁了几刀，你拿到手的是所有鸭子碎片而不是只有一个鸭屁股

那么在这种情况下，加入判断回文子串的代码好像有点不方便

所以我们改为在单层递归的时候做判断而不是在终止条件做判断

这样做同时也更省事了，如果你切了一刀发现这个不是回文串就没必要再切下去了

就好比切到鸭屁股的话扔掉就好了，没必要把鸭屁股也剁碎留着

还有一点需要明确的是分割完毕的表示方法，

在参数列表中我们不断传递的startindex实际上就对应我们砍下去的那一刀，

那么只要这个索引大于等于回文串长度就是切完了

if(startindex>=s.size()){

        result.push_back(path);

        return;

}

 3.确定单层遍历操作

还是同样的逻辑，最外层确定第一刀位置

切下来以后加入path中，再递归切第二刀...

递归结束后需要pop加入值，做一个回溯

除了以上切割操作，我们还需要加入判断回文串的代码

这一个部分为使效率最大化可以加在把碎片加入path的代码前

也就是说符合回文才加入path，否则直接return

判断回文串我们可以另设函数所以单层遍历操作应该如下:

for(int i=startindex;i<s.size();i++){

        if(isPalindrome(...){//这个函数等会再想！

                string str = s.substr(startindex,i-startindex+1);//当前碎片是【startindex,i】

                path.push_back(str);//是回文串！切下来放进path中！

        }else{

                continue;//不是就跳出！

        }

        backtracking(s,i+1);

        path.pop_back();

}       

补充：

s.substr(pos, len)

substr()是C++语言函数，主要功能是复制子字符串，要求从指定位置开始，并具有指定的长度。如果没有指定长度_Count或_Count+_Off超出了源字符串的长度，则子字符串将延续到源字符串的结尾。 

 ok那么回溯算法的步骤我们已经完成了，还剩下判断回文串的逻辑需要写

4.判断回文串

按照回文串的概念，我们只需要一个指针从头开始，一个指针从尾开始

不断同频比较两个字符是否相等就可以了

那么需要的参数就是这个字符串碎片

返回值设为bool类型

bool isPalindrome(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;

}

合并所有代码，并在主函数中传参调用即可！完整代码看下面👇！ 

code

class Solution {
public:
    vector<string> path;
    vector<vector<string>> result;
    bool isPalindrome(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;
    }
    void backtracking(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);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        backtracking(s,0);
        return result;
    }
};

题目二：复原IP地址

问题描述

93. 复原 IP 地址 - 力扣（LeetCode）

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

• 1 <= s.length <= 20
• s 仅由数字组成

解题步骤

参照上一题，我一开始写了以下代码，

主要思路就是无情分割，直到最后，

在每一步分割中使用函数判断是否符合要求

合理就加入path，逐渐组成IP地址

最后在叶子节点处加入正确的IP到result中

但是发现在单层递归中很难处理，

所以我们需要改变一下整个回溯的过程，按照这个题目的特点，给出量身定制的方案

class Solution {

public:

    string path;

    vector<string> result;

    bool isOK(string str){

        if(str.empty() || str.size()>3 || str[0]=='0'){

            return false;

        }

        int num=stoi(str);

        return num>=0&&num<=255;

    }

    void backtracking(string s,int startindex){

        if(startindex>=s.size()){

            result.push_back(path);

            return;

        }

        for(int i=startindex;i<s.size();i++){

            string str=s.substr(startindex,i-startindex+1);

            if(isOK(str)){

                path+=str;

               //@#@￥￥#%#！@@￥#@%！@？？？？？

            }else{

                break;

            }

            backtracking(s,i+1);

            path.pop_back();

        }

    }

    vector<string> restoreIpAddresses(string s) {

        if(s.size()<4 || s.size()>12){

            return result;

        }

        backtracking(s,0);

        return result;

    }

};

 再审审题！

IP地址是只能有4段的，每一段不超过3个数字，

所以这里我们需要把段数作为切割完成的标志，不能再用索引指到最后，

这样就相当于做数学证明题有条件没用上，那一般来说都是证不出来的！！！

那么和段数有关的还有IP地址中的 '.' （点），

为了一举两得（实现判断段数和加点）我们可以用点数来代表段数，

点数为3意味着段数为4嘛！

重新走一边回溯三部曲

1.确定函数返回值及参数

按照上面的思路，我们得加入段数作为参数，搭配startindex共同表示分割情况

startindex关乎下刀点，不能丢掉，把刀丢了还怎么切嘛！

void backtracking(string s,int startindex,int pointnum)

2.确定终止条件

上面已经捋清楚了:点数为3意味着段数为4

但是加入第三个点后我们还没有判断剩下部分，也就是第四段是否符合要求

所以这个最后一部分的合法性要放在这个终止条件中进行判断

合法后再加入到result中

if(pointnum==3){

        if(isValid...){//判断合法性等会再说！

                result.push_back(s);

        }

        return;      

}

 3.确定单层遍历操作

在单层遍历中我们需要往s中加点(题目说了可以通过在 s 中插入 '.' 来形成)，修改pointnum，递归，回溯

最外层遍历依旧代表第一刀（或者说上一刀）的位置，

这样才能确保第二🔪是从剩下的部分切的

切下来一段就需要判断是否合法

如果合法，在s的这个位置后面加上点

再让pointnum+1

递归backtracking函数

pointnum回溯，

s回溯

如果不合法，那么直接结束

for(int i=startindex;i<s.size();i++){

        if(isValid...){

                s.insert(s.begin()+i+1,'.');//加点

                pointnum++;

                backtracking(s,i+2,pointnum);//加入点后要再后挪一位！

                pointnum--;

                s.erase(s.begin()+i+1);

        }

        else

                break;

}

4.编写判断合法性函数

作为一个判断类的函数，返回值肯定是bool类型，

参数是为了传入待判断的片段，所以依旧是s，start，end

在函数体中利用if 判断IP地址一段的数字区间是否在[0,255],每一段开头第一个是否为0，区间长度是否小于等于3,该片段是否为空

否就返回false，都没有踩雷就返回true

bool isValid(string& s,int start,int end){   

        if (start > end || end - start + 1 > 3) {

            return false; // 片段为空或长度超过3

        }

        if (s[start] == '0' && start != end) {

            return false; // 前导0不合法

        }

        string str = s.substr(start, end - start + 1);

        int num = stoi(str);

        return num >= 0 && num <= 255;

}        

 最后整合代码，传入对应参数，在主函数中调用即可，

此外，在主函数中还可以加入一个剪枝，

如果字符串长度明显不符合IP地址的长度就不用调用回溯算法了

if(s.size()<=0 || s.size()>12)

        return result;

完整代码在下方！ 

code 

class Solution {
public:
    vector<string> result;

    bool isValid(string& s,int start,int end){
        if (start > end || end - start + 1 > 3) {
            return false; // 片段为空或长度超过3
        }
        if (s[start] == '0' && start != end) {
            return false; // 前导0不合法
        }
        string str = s.substr(start, end - start + 1);
        int num = stoi(str);
        return num >= 0 && num <= 255;
    }     
     
    void backtracking(string s,int startindex,int pointnum){
        if(pointnum==3){
            if(isValid(s,startindex,s.size()-1)){//最后一段！
                result.push_back(s);
            }
            return;
        }
        for(int i=startindex;i<s.size();i++){
            if(isValid(s,startindex,i)){
                s.insert(s.begin()+i+1,'.');//加点
                pointnum++;
                backtracking(s,i+2,pointnum);
                pointnum--;
                s.erase(s.begin()+i+1);
            }
            else
                break;
        }
    }

    vector<string> restoreIpAddresses(string s) {
        if(s.size()<=0 || s.size()>12)
            return result;
        backtracking(s,0,0);
        return result;
    }
};