## Description

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example: Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

## Analysis

1.第一种情况:长度大于3，必然是无效地址，返回false

2.第二种情况:首位为0，但其长度大于1,比如001。

3.第三种情况:大于255

class Solution {
bool isValidNum(string num){
if(num.size()>3||num[0]=='0'&&num.size()>1||num.empty()||stoi(num)>255)
return false;
return true;
}
void Dfs(string & str,int index,vector<string> & ipNum,vector<string> & ipComb){
if(ipNum.size()==4){
if(index==str.size()){
for(int i=1;i<4;i++)
}
return;
}
string curNum;
for(int i=index;i<str.size()&&i<index+3;i++){
curNum.push_back(str[i]);
if(isValidNum(curNum)){
ipNum.push_back(curNum);
Dfs(str,i+1,ipNum,ipComb);
ipNum.pop_back();
}
}
}
public:
vector<string> ipNum;
vector<string> ipComb;
Dfs(s,0,ipNum,ipComb);
return ipComb;
}
};


### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017