# 复原 IP 地址
给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 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 <= 3000s 仅由数字组成
以下错误的选项是？
## aop
### before
```c
#include
using namespace std;
```
### after
```c
int main()
{
Solution sol;
vector res;
string s = "25525511135";
res = sol.restoreIpAddresses(s);
for (auto i : res)
cout << i << " ";
return 0;
}
```
## 答案
```c
class Solution
{
public:
void dfs(vector &res, string &s, int start, vector &vec)
{
if (start == s.size())
{
if (vec.size() == 4)
{
string str;
int flag = 0;
for (int k = 0; k < 4; k++)
{
int num = atoi(vec[k].c_str());
if (num >= 0 && num <= 255)
{
str += vec[k];
}
if (k < 3)
{
str += '.';
}
}
if (flag == 0)
{
res.push_back(str);
}
}
return;
}
for (int i = start; i < s.size(); i++)
{
if (tmp != "0" && tmp.size() < 3)
{
tmp += s[i];
if (vec.size() < 4)
{
vec.push_back(tmp);
tmp = "";
dfs(res, s, i + 1, vec);
tmp = vec.back();
vec.pop_back();
}
}
}
}
vector restoreIpAddresses(string s)
{
int n = s.size();
vector res;
if (n < 4 || n > 12)
{
return res;
}
vector vec;
dfs(res, s, 0, vec);
return res;
}
private:
string tmp;
};
```
## 选项
### A
```c
class Solution
{
public:
vector res;
vector restoreIpAddresses(string s)
{
string temp = "";
dfs(s, temp, 0);
return res;
}
void dfs(string s, string &temp, int word_number)
{
if (word_number == 4)
{
if (s.empty())
res.push_back(temp);
}
else
{
if (word_number > 0)
temp += '.';
for (int i = 1; i <= 3 && i <= s.length(); i++)
{
if (valid(s.substr(0, i)))
{
temp += s.substr(0, i);
dfs(s.substr(i, s.length() - i), temp, word_number + 1);
temp = temp.substr(0, temp.length() - i);
}
}
temp.pop_back();
}
}
bool valid(const string &s)
{
if (s.empty() || (s[0] == '0' && s.size() > 1))
return false;
int val = stoi(s);
if (val >= 0 && val <= 255)
return true;
return false;
}
};
```
### B
```c
class Solution
{
public:
vector res;
bool isOk(int cnt, int beg, int len, string &s)
{
if (s.size() - beg < 4 - cnt || s.size() - beg > 3 * (4 - cnt))
return false;
string str = s.substr(beg, len);
if (len == 3 && stoi(str) > 255)
return false;
if (len >= 2 && str[0] == '0')
return false;
return true;
}
void backtrack(int cnt, int beg, string str, string &s)
{
if (cnt == 3)
{
if (isOk(cnt, beg, s.size() - beg, s))
res.push_back(str + s.substr(beg, s.size() - beg));
return;
}
for (int i = 1; i <= 3; ++i)
{
if (isOk(cnt, beg, i, s))
backtrack(cnt + 1, beg + i, str + s.substr(beg, i) + ".", s);
}
}
vector restoreIpAddresses(string s)
{
backtrack(0, 0, "", s);
return res;
}
};
```
### C
```c
class Solution
{
public:
vector restoreIpAddresses(string s)
{
int n = s.size();
if (n > 12 || n < 4)
return vector();
vector res;
string ans;
for (int i = 1; i <= 3; ++i)
{
if (n - i < 3 || n - i > 9)
continue;
string s1 = s.substr(0, i);
if (i == 3 && stoi(s1) > 255)
continue;
if (i == 2 && s1[0] == '0' || i == 3 && s1[0] == '0')
continue;
for (int j = 1; j <= 3; ++j)
{
if (n - i - j < 2 || n - i - j > 6)
continue;
string s2 = s.substr(i, j);
if (j == 3 && stoi(s2) > 255)
continue;
if (j == 2 && s2[0] == '0' || j == 3 && s2[0] == '0')
continue;
for (int k = 1; k <= 3; ++k)
{
if (n - i - j - k < 1 || n - i - j - k > 3)
continue;
string s3 = s.substr(i + j, k);
if (k == 3 && stoi(s3) > 255)
continue;
if (k == 2 && s3[0] == '0' || k == 3 && s3[0] == '0')
continue;
string s4 = s.substr(i + j + k, n - i - j - k);
if (stoi(s4) > 255)
continue;
if (n - i - j - k == 2 && s4[0] == '0' || n - i - j - k == 3 && s4[0] == '0')
continue;
res.push_back(s1 + "." + s2 + "." + s3 + "." + s4);
}
}
}
return res;
}
};
```