Generate All Possible IP Addresses From Given Numeric String in Java

1. Overview

In this tutorial, we’ll explore different ways to generate all possible IP Addresses from a given numeric string in Java. This problem is a common interview question. We’ll first deep-dive into the problem statement and then cover several techniques to solve it, including brute force, backtracking, and dynamic programming.

2. Understanding the Problem Statement

We’re given a string S which contains only digits, the goal is to find and return all possible valid IP addresses that can be formed by inserting dots into S. We can’t remove or reorder any digits; the result can be returned in any order.

For example, for a given string “101024”, we’ll have the following output:

["1.0.10.24","1.0.102.4","10.1.0.24","10.10.2.4","101.0.2.4"]

The output above lists all the valid IP addresses the given string can form. A valid IPv4 address consists of four octets separated by dots. Each octet is a number between 0 and 255. This means that a valid IPv4 address looks like:

0.0.0.0
192.168.0.8
234.223.43.42
255.255.255.0

3. Iterative Approach

In this approach, we’ll use three nested loops to iterate through possible positions to split the string into four parts. The outer loop iterates over the first part, the middle loop over the second part, and the inner loop over the third part. We’ll consider the remaining part of the string as the fourth segment.

Once we’ve got the segment combinations, we’ll extract sub-strings and validate each segment to determine if it forms a valid part of an IP address using the isValid() method. The isValid() method is responsible for checking if a given string is a valid part of an IP address or not. It makes sure that the integer value is between 0 and 255 and that it doesn’t have a leading zero:

public List<String> restoreIPAddresses(String s) {
    List<String> result = new ArrayList<>();

    if (s.length() < 4 || s.length() > 12) {
        return result;
    }

    for (int i = 1; i < 4; i++) {
        for (int j = i + 1; j < Math.min(i + 4, s.length()); j++) {
            for (int k = j + 1; k < Math.min(j + 4, s.length()); k++) {
                String part1 = s.substring(0, i);
                String part2 = s.substring(i, j);
                String part3 = s.substring(j, k);
                String part4 = s.substring(k);

                if (isValid(part1) && isValid(part2) && isValid(part3) && isValid(part4)) {
                    result.add(part1 + "." + part2 + "." + part3 + "." + part4);
                }
            }
        }
    }
    return result;
}

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

The method restoreIPAddresses() generates and returns all possible valid IP addresses. It also checks whether the string length falls outside the range of 4, and 12 characters and returns an empty list if it does, as a valid IP address can’t be formed in that case. 

We’re using nested loops to iterate over all possible positions for the three dots. This increases the time complexity to O(n²). It’s not O(n³) because the outer loop has a fixed number of iterations. Also, we’re creating temporary sub-strings during each iteration, which increases the overall space complexity to O(n).

4. Backtracking Approach

When backtracking, we generate all possible IP addresses by splitting the string into four parts. At each step, we perform the validation using the same isValid() method to check whether the string is non-empty and doesn’t have leading zeroes. If it’s a valid string we go to the next part. Once we’ve all four parts and have used all the characters, we’ll add them to the result list:

public List<String> restoreIPAddresses(String s) {
    List<String> result = new ArrayList<>();
    backtrack(result, s, new ArrayList<>(), 0);
    return result;
}

private void backtrack(List<String> result, String s, List<String> current, int index) {
    if (current.size() == 4) {
        if (index == s.length()) {
            result.add(String.join(".", current));
        }
        return;
    }

    for (int len = 1; len <= 3; len++) {
        if (index + len > s.length()) {
            break;
        }

        String part = s.substring(index, index + len);
        if (isValid(part)) {
            current.add(part);
            backtrack(result, s, current, index + len);
            current.remove(current.size() - 1);
        }
    }
}

The backtrack function splits the string into 4 integer segments, each at most 3 digits long. This leads to 3⁴ possible ways to split the string. Evaluating whether each segment is valid takes O(1) time, as it involves checking the length and range of the segment. Since the number of possible configurations 3⁴ is constant and doesn’t depend on the input string length, the time complexity simplifies to O(1).

The recursion depth is limited to 4 because there are exactly 4 segments in an IP address. Therefore, the space complexity simplifies to O(1) since the number of configurations and the space required are constants.

5. Dynamic Programming Approach

Dynamic programming is a popular algorithmic paradigm that uses a recurrent formula to find the solution. It is similar to the divide-and-conquer strategy because it breaks down the problem into smaller sub-problems. Its solutions use arrays to store the results of previously calculated values.

Now, we’ll use a dp array to store all valid IP prefixes. We’ll first initialize a 2D list dp where dp[i][j] stores all possible IP address segments up to the ith character with j segments. After this, we check for all possible segment lengths (1 to 3) and validate each segment using the isValid() method. If a segment is valid, we append it to the prefixes from the previous state. We store and return the final result of valid IP addresses in dp[n][4].

public List<String> restoreIPAddresses(String s) {
    int n = s.length();
    if (n < 4 || n > 12) {
        return new ArrayList<>();
    }

    List<String>[][] dp = new ArrayList[n + 1][5];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= 4; j++) {
            dp[i][j] = new ArrayList<>();
        }
    }

    dp[0][0].add("");

    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= 4; k++) {
            for (int j = 1; j <= 3 && i - j >= 0; j++) {
                String segment = s.substring(i - j, i);
                if (isValid(segment)) {
                    for (String prefix : dp[i - j][k - 1]) {
                        dp[i][k].add(prefix.isEmpty() ? segment : prefix + "." + segment);
                    }
                }
            }
        }
    }

    return dp[n][4];
}

Initialization of the dp array takes O(n*4) time, simplifying O(n). The nested loops responsible for filling the dp table take O(n*4*3) time simplifying to O(n). The space complexity is also O(n*4) which simplifies to O(n).

6. Conclusion

In this article, we discussed generating all possible IP address combinations from a given numeric string and understood various approaches to solve it. The iterative approach is straightforward but has a high time complexity O(n²). For better performance, we can use a dynamic programming approach which provides better time complexity of O(n).

The backtracking programming approach turned out to be the most efficient one as it had the best runtime O(1) amongst all the other approaches that we discussed.