Last Updated: 24 Dec, 2020

IP address

Easy

Asked in company

Solve now

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

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

Solve now

Approaches

01 Approach

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:

Each number lies between 0 and 255 inclusive. So, the maximum length of string S to generate a valid IP address can be 12.
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 :

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.
Create an empty array/list of strings, let’s say ‘ipAddress’ to store all possible IP addresses.
Let’s denote the length of the string using n.
We will use 3 nested loops to partition the string into 4 parts and check if all parts are valid.
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.
Repeat the above steps until we check all partitions.

Solve now

02 Approach

The idea is here to use backtracking to generate all possible IP addresses.

The key observation here is we can select either 1 or 2 or 3 digits at a time and put it into one segment.

So in each step, we will choose 1 or 2 or 3 digits and move to the next segment. Before moving to the next segment we will check if the current segment is valid or not. If it’s invalid then there is no need to proceed further with this address.

Steps :

We create an empty array/list of strings ‘ipAddress’ to store all possible IP addresses.
We create a function ‘backtracking’ which will take 5 arguments ‘validAddress’, ‘s’ (denoting original string), ‘curIndex’ (denoting current index), ‘segments’ (list used to store segments) and ‘segmentIndex’ (denoting the number of the current segment). Initially, we pass ‘curIndex’ = 0 and ‘segmentIndex’ = 0 as arguments.
If ‘curIndex’ = ‘n’ and ‘segmentIndex’ = 4, it means we have found a valid IP address. So, we add it to ‘ipAddress’ and return.
We run a loop from steps = 0 to 2.
1. Add s[curIndex] to segment[segmentIndex].
2. Then we will check if the current segment is valid or not.
  1. If the current segment is valid then we will recur for the next segment and increment both ‘curIndex’ and ‘segmentIndex’ by 1.
  2. Else we will move to the next iteration.
Finally, we return ‘ipAddress’ as our answer.

Solve now