IP address

Easy
0/40
1 upvote
Asked in company
Microsoft

Problem statement

You are given a string “S” containing only digits from 0 to 9. Your task is to find all possible IP addresses that can be obtained from S in lexicographical order. If no valid IP address can be generated from S, return an empty string.

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 if they are zero).

For example-
Following are valid IP addresses. 
0.1.24.255 
18.5.244.1

Following are invalid IP addresses. 
2.01.24.255 
18.312.244.1
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 test cases follow.

The only 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 separated by a single space. 

Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 1000  
0 <= |S| <= 15 

where |S| denotes the length of string, S.
S contains only digits from 0 to 9.

Time Limit: 1sec
Sample Input 1 :
2
00000
23579
Sample Output 1 :
2.3.5.79 2.3.57.9 2.35.7.9 23.5.7.9
Explanation :
For the first test case, no valid IP address can be found.

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
5555
02300
Sample Output 2 :
5.5.5.5
0.2.30.0 0.23.0.0
Explanation:
For the first test case, there is only one possible IP address that is 5.5.5.5.

For the second test case, all 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

In this solution, 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 final answer if it satisfies the following conditions:

  1. Each number lies between 0 and 255 inclusive. So, the maximum length of string S to generate a valid IP address can be 12.
  2. Each number must not contain leading zeroes(unless the number is 0 itself).

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

 

Steps :

  1. Create a function, let’s say ‘isValid’ which takes an argument ‘s’ as a string that is used to check the validity of a number in an IP address. It will return true if ‘s’ lies between 0 and 255 and ‘s’ do not contain leading zeroes.
  2. Create an empty array/list of strings, let’s say ‘ipAddress’ 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 = 1 to min(3, n) and do:
    1. Run a loop from j = i+1 to i+3 and do:
      1. Run a loop from k = j+1 to j+3 and do:
        1. Let’s denote substring from index ‘x’ to ‘y’ as substr(x, y)
        2. If isValid(substr(0, i)) and isValid(substr(i+1, j)) and isValid(substr(j+1,k)) and isValid(substr(k+1,n)) is true, then add this partition to ‘ipAddress’.
        3. Else, move to the next partition.
  6. Repeat the above steps until we check all partitions.
Time Complexity

O(1).

 

We are using 3 nested loops, the outer loop runs for min(3, N) times while both inner loops run 3 times. Since the maximum length of S to generate a valid IP address can be 12, the overall time complexity is constant.

Space Complexity

O(1), constant space is used.

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