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

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.