复原IP地址-leetcode-93
目录
复原IP地址 （leetcode 93
leetcode系列
一、核心操作
- 判断字段是否有效函数：首先start不能大于end
当到最后一个收获层的时候，start已经是s.size了，但是end还是只能是s.size-1其次当字段不止一位时，start不能是0，然后再循环判断每一位是不是处于字符‘0’和‘9’之间，以及通过num*10+当前数字的操作求出值，判断是不是大于255 - 回溯函数：传参中多了一个pointNum，用于判断有几个点，如果到了3个点，就把剩下的字段传入 是否有效函数 如果有效就可以收获结果了，并且不管有没有收获，到了3个点就要返回。在每一层的循环中，对于字段的有效性做出判断，如果有效则在i的后面位置加点，并将pointNum++，
注意由于加了点，输入下一层的startIndex是i+2，并进行回溯；如果无效的话直接break
提示：小白个人理解，如有错误敬请谅解！
二、外层配合操作
- 调用回溯函数
三、核心模式代码
代码如下：
class Solution {
public:
vector<string> res;
bool isValid(string s, int start, int end)
{
if(start>end)return false;
if(s[start]=='0' && start!=end)return false;
if((end-start+1)>3)return false;
int num=0;
for(int i=start;i<=end;i++)
{
if(s[i]>'9' || s[i]<'0')return false;
num=num*10+(s[i]-'0');
if(num>255)return false;
}
return true;
}
void backtracking(string s, int startIndex, int pointNum)
{
if(pointNum==3){
if(isValid(s,startIndex,s.size()-1))
res.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);
s.erase(s.begin()+i+1);
pointNum--;
}
else break;
}
}
vector<string> restoreIpAddresses(string s) {
if(!s.size())return res;
backtracking(s,0,0);
return res;
}
};总结
- 需要多注意字段有效性的判断