93. Restore IP Addresses

2019-07-27

93. Restore IP Addresses

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

Example:

1
2
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
     def restoreIpAddresses(self, s):
        ret = []
        for a in range(1, 4):
          for b in range(1, 4):
            for c in range(1, 4):
              d = len(s) - a - b - c
              """
              Last number must use all remaining digits. Check;
              1. The size of the last number is valid
              2. Every number uses 1 digit for 0 and is less than 255 if using 3 digits
              """
              if (1 <= d <= 3 and
                (1 == a or '0' != s[0        ]) and (a != 3 or s[         :a        ] <= "255") and
                (1 == b or '0' != s[a        ]) and (b != 3 or s[a        :a + b    ] <= "255") and
                (1 == c or '0' != s[a + b    ]) and (c != 3 or s[a + b    :a + b + c] <= "255") and
                (1 == d or '0' != s[a + b + c]) and (d != 3 or s[a + b + c:         ] <= "255")):
                ret.append('.'.join([s[0:a], s[a:a + b], s[a + b:a + b + c], s[a + b + c:]]))
        return ret
-->