 8

Difficulty: MEDIUM Contributed By
Shivam Kumar Singh
Avg. time to solve
15 min
Success Rate
85%

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.
``````
##### 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]
``````   Console