Restore IP Addresses

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
36 upvotes
Asked in companies
FacebookAppleMicrosoft

Problem statement

You are given a string 'S' containing only digits. Your task is to find all possible IP addresses that can be obtained from string 'S' in lexicographical order.

Note: 
A valid IP address consists of exactly four integers, each integer is between 0 and 255 separated by single dots, and cannot have leading zeros except in the case of zero itself.
For example: 
The following are valid IP addresses:
0.1.24.255
18.5.244.1

Following are invalid IP addresses:
0.01.24.255  (as  01  contains one leading zero).
18.312.244.1 (as 312 not lies between 0 and 255).
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. 

Then the 'T' test cases follow.

The first line of each test case contains a string 'S'.
Output format : 
For each test case, print a single line containing all possible valid IP addresses that can be obtained from 'S' in lexicographical order in a separate line.

Each IP address of a string 'S' is written within quotes("") and separated by comma(,) and space, and all IP addresses of the given string 'S' is written inside square brackets[].
Constraints: 
1 <= T <= 1000
1 <= |S| <= 15

Where |'S'| denotes the length of string 'S' and 'S' contains only digits from 0 to 9.

Time Limit: 1 sec
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1 :
2 
2122
23579
Sample Output 1 :
[“2.1.2.2”]
[“2.3.5.79”, “2.3.57.9”, “2.35.7.9”, “23.5.7.9”]
Explanation for sample Input 1:
For the first test case, there is only one possible IP address that is [2.1.2.2]

For the second test case, all possible IP addresses are shown below.
[2.3.5.79], [2.3.57.9], [2.35.7.9], [23.5.7.9]
Sample Input 2 :
2
123
02300
Sample Output 2 :
[]
[“0.2.30.0”, “0.23.0.0”]
Explanation for sample Input 2:
For the first test case, there is no possible IP address. Therefore then answer is []

For the second test case, there are only 2 possible IP addresses are shown below.
[0.2.30.0], [0.23.0.0]
Hint

Think of a solution using nested for loops.

Approaches (2)
Brute Force

The idea is to divide the given string into 4 parts using 3 dots, where each part corresponds to a number. Then we will add the current IP address to answer if it satisfies the following conditions:

  1. Each number lies between 0 and 255 inclusive.
  2. Each number must not contain leading zeroes.

So we will run 4 nested loops from 1 to 3. 

 

Steps :

  1. Create a function, let’s say check which takes an argument s as a string that is used to check the validity of a number in a current IP address. It will return true if s lies between 0 and 255 and s do not contain leading zeroes.
  2. Create an empty list of strings, let’s say answer to store all possible IP addresses.
  3. Let’s denote the length of the string using n.
  4. We will use 3 nested loops to partition the string into 4 parts and check if all parts are valid.
  5. Run a loop from i = 0 to min(3,n-3) and do:
    • Run a loop from j = i+1 to min(i+3,n-3) and do:
      • Run a loop from k = j+1 to min(j + 3, n - 2) and do:
        • Let’s denote substring from x to y as substr(x,y),Now check If check(substr(0,i)) ,check(substr(i+1,j)) ,check(substr(j+1,k)), and check(substr(k+1,n-1)) is true then add this partition to answer.
        • Else move to the next partition.
  6. Repeat step 5 until you check all partitions
Time Complexity

O(1).

 

In the worst case,  we are using three for loops which takes constant time, and the check function also takes constant time. Hence the overall time complexity will be O(1).

Space Complexity

O(1).

 

As we use constant space.

Code Solution
(100% EXP penalty)
Restore IP Addresses
Full screen
Console