Recovering IPv4 Addresses

You are given a String containing at least 4 numbers that represented an IPv4 Address, but the separator data - i.e. the dots that separate each Byte in a 4 Byte Ipv4 address, has been lost. Write a method - generateIPAddrs that takes in this String and returns an ArrayList of Strings containing all possible IPv4 Addresses that can be generated from the given sequence of decimal integers.

Note:

- The IP Addresses for this problem are written in the decimal dot notation.
- You must use all the digits in the input String
- The order in which the IP Addresses are returned does not matter
- 0.0.0.1 and 0.0.0.01 may be considered 2 distinct possibilities. i.e. do not ignore leading or trailing 0s.

Examples:

generateIPAddrs("1001") ==> {"1.0.0.1"}

generateIPAddrs("1010") ==> {"1.0.1.0"}

generateIPAddrs("25525511135") ==> {"255.255.11.135", "255.255.111.35"}

Need a hand? Try out these hints, one at a time.

Quick hint to get things rolling

IPv4 addresses are 32-bit numbers, with each 8-bit group being separated by a period. The range of each 8 bit group is between [0-255], as the max number possible with an 8 bit number is 256-1 = 255.

A more detailed explanation

This is a classic Depth First Search problem, and can be solved recursively or iteratively. BFS and DFS are slightly easier to visualize if coded iteratively - and for the subsequent hints, we'll be using a Stack to perform a classic DFS for this problem. Since we need to preserve some information as we build our stack, we'll create a local class - IpLevelNode that stores the IP Address generated to that point, as well as the level and remaining numbers available.

Final hint! You should be able to code the problem on viewing this.

1. Initialize an ArrayList to store all the possible IP Addresses.
2. Create a local class - IpLevelNode that stores the IP Address generated to that point (predecessor), as well as the level (level) and remaining numbers available (successor).
3. Use a Deque as a stack.
4. In this algorithm, for each 8-bit group, we'll partition the level to create 3 new nodes. For eg, 222 can be partitioned as 2.22, 22.2 and 222.
5. Perform DFS after pushing on the first 3 nodes.
6. Before pushing additional nodes onto the stack, make sure that the range of the IP Address is not violated. All groups must lie between 0 and 255.
7. At the last level of the DFS, if an IpLevelNode has no additional numbers remaining in its successor, add the predecessor of this node to the output ArrayList.

public static ArrayList<String> generateIPAddrs(String s) {

}

This Coding Interview Question is available with an answer in the following programming languages :

Java

Python

Recovering IPv4 Addresses

Quick hint to get things rolling

A more detailed explanation

Final hint! You should be able to code the problem on viewing this.

The interview prep tool you'll fall in love with!

This Coding Interview Question is available with an answer in the following programming languages :