IP Address

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).

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:

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

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

Steps :

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.
Create an empty list of strings, let’s say answer 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 = 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.
Repeat step 5 until you check all partitions

Try Problem

Approach 2

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 visit this path.

Backtracking Approach consist of the following things :

Base cases: They are used to check whether current path is valid or not.
Constraints: This part is used to define how many steps we need to move or how many digits we need to take and if we move these many steps then our current segment will remain valid or not. If the current segment remains valid then we will move to the next segment and explore this part else we move to the next iteration to select more number of the steps.
Exploration: In this, we will explore this path as we know this path is valid and move to the next segment. And finally, we will clear this segment to backtrack for the next path.

Steps :

Create a function, let’s say check which takes an argument 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 list of strings, let’s say answer that is used to store all possible IP addresses.
Let’s denote length of string using N.
Create a function let’s say backtracking which will take 5 arguments answer, s, denoting original string, curIndex, denoting current index, segments, used to store segments, segmentIndex, denotes the current number of segment we currently in.
We will pass curIndex = 0 and segmentIndex = 0 as arguments in the backtracking function.
Call function backtracking to get the answer.

void backtracking(s, answer,segments, curIndex, segmentIndex):

We define base cases :
- If curIndex = n then if segmentIndex = 4 then add the current path to answer, and then return.
- If curIndex < n then if segmentIndex > 4 then also break the recursion.
Define constraints i.e., Run a loop from steps = 0 to 2 and do :
- Add s[curIndex+steps] to segment[segmentIndex].
- If curIndex < n then if segmentIndex > 4 then also break the loop.
- If the current segment is valid then we will recur for the next segment and increment both curIndex and segmentIndex by 1.
- Else we will move to the next iteration.