Posted: 28 Dec, 2020
Difficulty: Moderate

## 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

0.01.24.255  (as  01  contains one leading zero).
18.312.244.1 (as 312 not lies between 0 and 255).
``````
##### 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.
``````
Approach 1

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