Restore IP Addresses

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

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 :

1. Base cases: They are used to check whether current path is valid or not.
2. 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.
3. 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 :

1. 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.
2. Create an empty list of strings, let’s say answer that is used to store all possible IP addresses.
3. Let’s denote length of string using N.
4. 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.
5. We will pass curIndex = 0 and segmentIndex = 0 as arguments in the backtracking function.
6. Call function backtracking to get the answer.

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

1. 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.
2. 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.