【LeetCode回溯算法#06】复原IP地址详解（练习如何处理边界条件，判断IP合法性） - da...

复原IP地址

力扣题目链接(opens new window)

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

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

例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 无效的 IP 地址。

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

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

• 输入：s = "1111"
• 输出：["1.1.1.1"]

• 输入：s = "010010"
• 输出：["0.10.0.10","0.100.1.0"]

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

• 0 <= s.length <= 3000
• s 仅由数字组成

实际上还是分割问题，但是又多了一些条件

本题的麻烦的点在于有很多边界条件需要处理

待解决的问题有：

1、如何加入分割点

2、如何判断分割的段落是否为合法IP

插入分割点

"分割"这个动作与 分割回文串 里定义的一致，都是用beginIndex指到分割位置

不同的是，这里我们beginIndex指到分割的位置时，我们需要在这个位置的后一位插入分割点

（后面细说）

合法IP判断

这里我们需要写一个判断函数来判断IP 是否合法，函数的输入是字符串和待判断的区间

bool isVaild(string& s, int start, int end){
    
}

这里本质上我们还是在s上操作，只是指定了操作的位置

首先需要明确非法IP的情况：

​ 0、所给的判断区间不合法

​ 1、以0开头的数字，例如：192 . 031 . 2 . 1

​ 2、负数

​ 3、IP段数值大于255

bool isVaild(string& s, int start, int end){
    if(start > end) return false;//所给的判断区间不合法
    
    //是否以0开头
    if(s[start] == '0' && start != end) return false;
    
    int num4IP = 0;
    for(int i = start; i < end; ++i){
        //是否为正数
        if(s[i] < 0 && s[i] > 9) return false;
        
        //IP段数值是否大于255
        num4IP = num4IP * 10 + (s[i] - '0');
        if(num4IP > 255) return false;        
    }
    return true;
}

这里有几个关键点：

1、判断是否有IP段以0开头

请注意，我们这里判断的是false的情况，也就是有IP段使用了0开头

判断条件除了直接看开头字符是否为0（s[start] == '0'）以外，还需要确保当前IP段的数字不是第一个获取到的，因此需要追加条件 start != end

什么意思呢？这里又涉及到单层处理中的逻辑

在单层处理时，我们会去遍历由beginIndex控制的s中的区间，每次遍历都会触发isVaild函数来判断当前遍历所得的IP段是否合法

isVaild函数需要输入一个判断区间（这个区间其实就是[beginIndex, i]）

当第一次遍历的时候，输入isVaild的区间是[0, 0]，此时会出现一种特殊情况

例如，我们的数字字符串是：s = "0000"

那么第一次遍历获取IP段时，我们得到的是'0'，从我们的角度来看，这种情况应该是合法的

如果我们不追加条件去判断当前遍历是不是第一次遍历，那么上述情况会被程序视为非法，就会导致错误

为什么start != end可以判断遍历是否为第一次遍历？

前面也说过了，因为我们输入的区间实际上是[beginIndex, i]，那么这个区间只有在第一次遍历时才会出现左右边界相等的情况，即[0, 0]

2、判断IP段数值大于255

这里容易犯的一个错误是直接拿s[i]来和255进行大小判断

拜托，s[i]是什么？它是组成当前IP段的数字之一，单个数字怎么可能大于255，这样判断只会通过所有的情况

因此，这里需要一点小小的计算，我来模拟一下这个过程

	int num4IP = 0;
    for(int i = start; i < end; ++i){
        //是否为正数
        if(s[i] < 0 && s[i] > 9) return false;
        
        //IP段数值是否大于255
        num4IP = num4IP * 10 + (s[i] - '0');
        if(num4IP > 255) return false;        
    }

例如当前的IP段是164，

第一轮遍历拿到s[i]是1，此时num = 0 * 10 + ('2' - '0') = 1

第二轮遍历拿到s[i]是6，此时num = 1 * 10 + ('5' - '0') = 16

第三轮遍历拿到s[i]是4，此时num = 16 * 10 + ('4' - '0') = 164

164显然是满足条件的

发现没有， num = num * 10 + (s[i] - '0');的作用就是把数据类型为字符串的IP段转化为整型，然后再判断

开始写，还是老一套，回溯三部曲

1、确定回溯函数的参数和返回值

本题中我们是直接操作的数字字符串s，因此不需要返回值

输入参数是数字字符串s、beginIndex和countPoint

countPoint用于统计目前一共插入了几个分割点，用于终止判定

class Solution {
private:
    bool isVaild(string& s, int start, int end){
        ...
    }
    vector<string> res;
    //确定回溯函数的参数和返回值
    //参数：数字字符串、beginIndex、分割点计数变量
    void backtracking(string& s, int beginIndex, int countPoint){        
    }
public:
    vector<string> restoreIpAddresses(string s) {        
    }
};

2、确定终止条件

这里就用到countPoint了

参考IP的结构，当我们已经插入了3个分割点时，这时需要结束了（不论之后还剩什么）

同时，我们还要判断一下被分割出来的第四段是否合法，合法就把当前插好的数字字符串s保存到结果数组（一定记得我们是对s进行操作，最后的结果也是处理好的s）

class Solution {
private:
    bool isVaild(string& s, int start, int end){
        ...
    }
    vector<string> res;
    //确定回溯函数的参数和返回值
    //参数：数字字符串、beginIndex、分割点计数变量
    void backtracking(string& s, int beginIndex, int countPoint){
        if(countPoint == 3){
            if(isVaild(s, beginIndex, s.size() - 1)){//判断第四段是否合法
                res.push_back(s);                
            }
            return;
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {        
    }
};

3、确定单层处理逻辑

在单层递归中，我们需要遍历由beginIndex控制的当前区间

使用for循环不断获取IP段，然后判断其是否合法

合法就在当前位置 i 的后一个位置插入分割点

class Solution {
private:
    bool isVaild(string& s, int start, int end){
        ...
    }
    vector<string> res;
    //确定回溯函数的参数和返回值
    //参数：数字字符串、beginIndex、分割点计数变量
    void backtracking(string& s, int beginIndex, int countPoint){
        //确定终止条件
        //当分割点的数量达到3个时说明分割结束，此时字符串已经被分成4段
        //在这里还需要验证最后一段是否合法
        if(countPoint == 3){
            if(isVaild(s, beginIndex, s.size() - 1)){//判断第四段是否合法
                res.push_back(s);                
            }
            return;
        }
        //确定单层处理逻辑
        for(int i = beginIndex; i < s.size(); ++i){
            //这里beginIndex不是固定的，下一层递归时beginIndex会由上一层递归传入
            if(isVaild(s, beginIndex, i)){                
                s.insert(s.begin() + i + 1, '.');//插入分割点
                countPoint++;//计数++
                backtracking(s, i + 2, countPoint);//只加1的话就到分割点的位置，所以得多加一个
                countPoint--;//回溯
                s.erase(s.begin() + i + 1);
            }
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {        
    }
};

这里又涉及到一个边缘处理问题：插入分割点的位置

题外话：insert函数

本题中使用insert来在s中插入分割点

举个例子说明insert的使用：

teststr = "1234";
teststr.insert(1, '.');//在原串下标为1的字符1前插入'.'->"1.234"

所以为什么插分割点的时候的位置是s.begin() + i + 1

因为s.begin() + i只定位到了当前指针 i 遍历到的位置，而我们希望在该位置之后加点，所以要再加1

例如遍历"1234"，遍历时 i 指向2时，即下标2，我们需要在2后面打点，此时要输入insert的应该是下标3而不是下标2

本题思路很清晰，但是难点在于有很多的边界条件

一旦处理不好或者忘了，就会出错

class Solution {
private:
    bool isVaild(string& s, int start, int end){
        //判断区间是否合法
        if(start > end) return false;
        //判断数字开头是否为0，为0非法
        if(s[start] == '0' && start != end){
            return false;
        }
        int num4IP = 0;
        //遍历待判断区间
        for(int i = start; i <= end; ++i){
            //是否为正数
            if(s[i] > '9' || s[i] < '0'){
                return false;
            }
            //是否在255范围内
            num4IP = num4IP * 10 + (s[i] - '0');
            if(num4IP > 255){
                return false;
            }
        }
        return true;
    }
    vector<string> res;
    //确定回溯函数的参数和返回值
    //参数：数字字符串、beginIndex、分割点计数变量
    void backtracking(string& s, int beginIndex, int countPoint){
        //确定终止条件
        //当分割点的数量达到3个时说明分割结束，此时字符串已经被分成4段
        //在这里还需要验证最后一段是否合法
        if(countPoint == 3){
            if(isVaild(s, beginIndex, s.size() - 1)){//判断第四段是否合法
                res.push_back(s);                
            }
            return;
        }
        //确定单层处理逻辑
        for(int i = beginIndex; i < s.size(); ++i){
            //这里beginIndex不是固定的，下一层递归时beginIndex会由上一层递归传入
            if(isVaild(s, beginIndex, i)){                
                s.insert(s.begin() + i + 1, '.');//插入分割点
                countPoint++;//计数++
                backtracking(s, i + 2, countPoint);//只加1的话就到分割点的位置，所以得多加一个
                countPoint--;//回溯
                s.erase(s.begin() + i + 1);
            }
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {
        //这里可以先判断一下字符串s是否合法
        if(s.size() < 4 || s.size() > 12) return res;
        backtracking(s, 0, 0);
        return res;
    }
};