复原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" 和 "192.168@1.1" 是 无效的 IP 地址.

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

• 输入：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;
    }
};

                        
                      

最后此篇关于【LeetCode回溯算法#06】复原IP地址详解（练习如何处理边界条件，判断IP合法性）的文章就讲到这里了,如果你想了解更多关于【LeetCode回溯算法#06】复原IP地址详解（练习如何处理边界条件，判断IP合法性）的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。