# Problem Solving – IP addresses must follow the format A.B.C.D, where A, B, C, and D are numbers between 0 and 255.

By | June 19, 2023

Given a string of digits, generate all possible valid IP address combinations. IP addresses must follow the format A.B.C.D, where A, B, C, and D are numbers between 0 and 255. Zero-prefixed numbers, such as 01 and 065, are not allowed, except for 0 itself. For example, given “2542540123”, you should return [‘254.25.40.123’, ‘254.254.0.123’].

To generate all possible valid IP address combinations from a given string of digits, we can use a recursive approach. Here’s the solution:

Solution – Python

```def restoreIpAddresses(s):
if len(s) > 12 or len(s) < 4:  # Check if the string length is within the valid range
return []

result = []
dfs(s, "", result, 0)
return result

def dfs(s, ip, result, count):
if count == 3 and isValid(s):
result.append(ip + s)
return

for i in range(1, 4):
if isValid(s[:i]):
dfs(s[i:], ip + s[:i] + ".", result, count + 1)

def isValid(s):
if len(s) > 1 and s[0] == '0':  # Check for leading zeros, except for '0' itself
return False
if int(s) > 255:  # Check if the number is within the valid range
return False
return True

```

Solution – Java

```
import java.util.ArrayList;
import java.util.List;

public class IPAddressesGenerator {
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
if (s.length() > 12 || s.length() < 4) {
return result;
}

dfs(s, "", result, 0);
return result;
}

private void dfs(String s, String ip, List<String> result, int count) {
if (count == 3 && isValid(s)) {
result.add(ip + s);
return;
}

for (int i = 1; i <= 3; i++) {
if (isValid(s.substring(0, i))) {
dfs(s.substring(i), ip + s.substring(0, i) + ".", result, count + 1);
}
}
}

private boolean isValid(String s) {
if (s.length() > 1 && s.charAt(0) == '0') {
return false;
}
int num = Integer.parseInt(s);
return num >= 0 && num <= 255;
}

public static void main(String[] args) {
IPAddressesGenerator generator = new IPAddressesGenerator();
List<String> ipAddresses = generator.restoreIpAddresses("2542540123");
for (String ipAddress : ipAddresses) {
System.out.println(ipAddress);
}
}
}
```

Explanation

• The `restoreIpAddresses` function is the main function that generates all possible IP addresses. It first checks if the length of the input string `s` is within the valid range (4 to 12 digits). If not, it returns an empty list as there are no valid IP addresses possible.
• It initializes an empty `result` list to store the valid IP address combinations.
• It then calls the `dfs` (depth-first search) function to recursively generate all possible IP addresses.
• The `dfs` function takes the input string `s`, the current partial IP address `ip`, the `result` list, and a `count` parameter that keeps track of the number of segments in the IP address.
• If `count` is equal to 3 (indicating we have already generated three segments) and the remaining part of `s` is a valid segment, it appends the complete IP address to the `result` list.
• Otherwise, it iterates from 1 to 3 (as each segment can have a maximum of 3 digits) and checks if the first `i` digits of `s` form a valid segment. If so, it recursively calls `dfs` with the remaining part of `s` and updates the current IP address `ip` by adding the valid segment followed by a dot.
• The `isValid` function is a helper function that checks if a given segment is valid. It first checks if the segment has leading zeros (except for the digit ‘0’ itself), and then checks if the segment is within the valid range of 0 to 255.

By applying the `restoreIpAddresses` function to the given input “2542540123”, it will return `['254.25.40.123', '254.254.0.123']`, which are all the possible valid IP address combinations for the given string of digits.