复原IP地址
给定一个只包含数字的字符串,复原它并返回所有可能的 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 地址。
示例 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;
}
};
标签:分割,beginIndex,06,int,IP,start,IP地址,return
From: https://www.cnblogs.com/DAYceng/p/17204129.html