solution.md

# 复原 IP 地址

<p>给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 <code>s</code> 获得的 <strong>有效 IP 地址 </strong>。你可以按任何顺序返回答案。</p><p><strong>有效 IP 地址</strong> 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 <code>0</code>），整数之间用 <code>'.'</code> 分隔。</p><p>例如："0.1.2.201" 和 "192.168.1.1" 是 <strong>有效</strong> IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 <strong>无效</strong> IP 地址。</p><p> </p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>s = "25525511135"<strong><br />输出：</strong>["255.255.11.135","255.255.111.35"]</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>s = "0000"<strong><br />输出：</strong>["0.0.0.0"]</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>s = "1111"<strong><br />输出：</strong>["1.1.1.1"]</pre><p><strong>示例 4：</strong></p><pre><strong>输入：</strong>s = "010010"<strong><br />输出：</strong>["0.10.0.10","0.100.1.0"]</pre><p><strong>示例 5：</strong></p><pre><strong>输入：</strong>s = "101023"<strong><br />输出：</strong>["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>0 <= s.length <= 3000</code></li>	<li><code>s</code> 仅由数字组成</li></ul>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    vector<string> res;
    string s = "25525511135";
    res = sol.restoreIpAddresses(s);
    for (auto i : res)
        cout << i << " ";
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    void dfs(vector<string> &res, string &s, int start, vector<string> &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<string> restoreIpAddresses(string s)
    {
        int n = s.size();
        vector<string> res;
        if (n < 4 || n > 12)
        {
            return res;
        }
        vector<string> vec;
        dfs(res, s, 0, vec);
        return res;
    }

private:
    string tmp;
};
```
## 选项


### A

```cpp
class Solution
{
public:
    vector<string> res;
    vector<string> 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

```cpp
class Solution
{
public:
    vector<string> 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<string> restoreIpAddresses(string s)
    {
        backtrack(0, 0, "", s);
        return res;
    }
};
```

### C

```cpp
class Solution
{
public:
    vector<string> restoreIpAddresses(string s)
    {
        int n = s.size();
        if (n > 12 || n < 4)
            return vector<string>();
        vector<string> 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;
    }
};
```