restore-ip-addresses
2019-07-17 本文已影响0人
DaiMorph
//IP地址每个字段可能是1位数,2位数或者3位数,每一个字段都位于1~255之间
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string>res;
dfs(s,0,"",res);
return res;
}
void dfs(string s,int n,string out,vector<string>&res)
{
if(s.size()==0&&n==4)
{
res.push_back(out);
return;
}
for(int k=1;k<4;k++)
{
if(s.size()<k)return;
int value=atoi(s.substr(0,k).c_str());
if(value>255||k!=to_string(value).size())return;//出现0x之后,后面的都是0xxxxx,都不合法
dfs(s.substr(k),n+1,out+s.substr(0,k)+(n==3?"":"."),res);
}
}
};