题目链接：Restore IP Addresses

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)

这道题的要求是将一个只包含数字的字符串重新存储成IP地址的形式，返回所以情况。

注：这里的IP地址是指IPv4地址。

IP地址是指互联网协议地址（英语：Internet Protocol Address，又译为网际协议地址），是IP Address的缩写。IP地址是IP协议提供的一种统一的地址格式，它为互联网上的每一个网络和每一台主机分配一个逻辑地址，以此来屏蔽物理地址的差异。

IP地址是一个32位的二进制数，通常被分割为4个“8位二进制数”（也就是4个字节）。IP地址通常用“点分十进制”表示成（a.b.c.d）的形式，其中，a,b,c,d都是0~255之间的十进制整数。例：点分十进IP地址（100.4.5.6），实际上是32位二进制数（01100100.00000100.00000101.00000110）。

因此，需要判断一个数字字符串是否符合IP地址中的一组IP字段（即两个点分割的数字），符合的情况分为如下几种：（这里的IP字段指的是0~255）

  • 任意单个数字（0也是符合的）；
  • 两个数字，则高位不为0；
  • 三个数字，则最高位为1或者2，且小于等于255，即最高位为1 或者 最高位为2且第二位小于5 或者 最高位为2且第二位等于5且最低位小于等于5。

  1. 递归回溯

思路就是如果字符串s的前半部分已经生成了m个IP字段，则递归处理s的后半部分，使其生成4-m个IP字段即可。

b是字符串中字符的开始位置，n表示还需生成IP地址中的几个IP字段，ip表示已经生成的IP地址。

递归终止条件是n为0，此时如果扫描到字符串的最后，即b等于字符串长度，说明生成的IP地址符合要求，存储起来即可。

时间复杂度：O(???)

空间复杂度：O(???)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution
{
    vector<string> vs;
public:
    vector<string> restoreIpAddresses(string s)
    {
        restoreIpAddresses(s, 0, 4, "");
        return vs;
    }
private:
    void restoreIpAddresses(string &s, int b, int n, string ip)
    {
        if(n == 0)
        {
            if(b == s.size())
                vs.push_back(ip);
            return;
        }
        
        for(int i = b + 1; i <= s.size(); ++ i)
        {
            string temp = s.substr(b, i - b);
            if(isIP(temp))
                restoreIpAddresses(s, i, n - 1, ip == "" ? temp : ip + "." + temp);
            else
                break;
        }
    }
    bool isIP(string s)
    {
        if(s.size() == 1 || (s.size() == 2 && s[0] != '0') || (s.size() == 3 &&
            (s[0] == '1' || s[0] == '2' && (s[1] < '5' || s[1] == '5' && s[2] <= '5'))))
            return true;
        return false;
    }
};

  1. 字符串分割

由于IP地址分为4段，因此，可以考虑把字符串S分割成4段，并且每段最多3个数字字符。如果这四段都符合IP字段的要求，则表明此种分割方式可以生成IP地址，存储起来即可。

时间复杂度：O(???)

空间复杂度：O(???)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution
{
public:
    vector<string> restoreIpAddresses(string s)
    {
        vector<string> vs;
        for(int i = 1; i < 4 && i < s.size(); ++ i)
            for(int j = i + 1; j < i + 4 && j < s.size(); ++ j)
                for(int k = j + 1; k < j + 4 && k < s.size(); ++ k)
                {
                    string s1 = s.substr(0, i), s2 = s.substr(i, j - i), 
                           s3 = s.substr(j, k - j), s4 = s.substr(k, s.size() - k);
                    if(isIP(s1) && isIP(s2) && isIP(s3) && isIP(s4))
                        vs.push_back(s1 + "." + s2 + "." + s3 + "." + s4);
                }
        return vs;
    }
private:
    bool isIP(string s)
    {
        if(s.size() == 1 || (s.size() == 2 && s[0] != '0') || (s.size() == 3 &&
            (s[0] == '1' || s[0] == '2' && (s[1] < '5' || s[1] == '5' && s[2] <= '5'))))
            return true;
        return false;
    }
};