You are given a

**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:

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

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.

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.
1. Initialize an

2. Create a

3. Use a

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

`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) { }

**C**

**Java**

**Python**