给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"]
题目很简单但是，需要特定判断的情况很多。
思路可以是递归和多重循环，。
因为该题没有太需要用到递归，所以直接用循环。
易错的地方会在代码中标注。
class Solution
{
public:
vector<string> restoreIpAddresses(string s)
{
vector<string> res;
int len = s.size();
///第一次
for (int i = 1; i <= 3; i++)
{
//判断是否超过了字符串的长度，除了最后一次，都要需要判断
if (i >= len)
continue;
string str1 = string(s.begin(), s.begin() + i);
//检查字符串是否符合要求
if (!Check(str1))
continue;
///第二次
for (int j = 1; j <= 3; j++)
{
if (i + j >= len)
continue;
string str2 = string(s.begin() + i, s.begin() + i + j);
if (!Check(str2))
continue;
///第三次和第四次
for (int k = 1; k <= 3; k++)
{
if (i + j + k >= len)
continue;
string str3 = string(s.begin() + i + j, s.begin() + i + j + k);
if (!Check(str3))
continue;
string str4 = string(s.begin() + i + j + k, s.end());
if (!Check(str4))
continue;
res.push_back(str1 + '.' + str2 + '.' + str3 + '.' + str4);
}
}
}
return res;
}
bool Check(string s)
{
//检测最后一个字符串str4是否为空
if (s.size() == 0)
return false;
//判断是否有011,01这种以0开头的字符串
if (s[0] == '0' && s.size() > 1)
return false;
int number = 0;
for (int i = 0; i < s.size(); i++)
{
number = number * 10 + (s[i] - '0');
//需要在里面进行判断是否超出范围
//因为number是字符串转来的，很可能超出了int的范围，超出后变成负数判断就比255小，返回true，显然这是不正确的
//所以在循环里面提前判断
if (number > 255)
return false;
}
return true;
}
};