Solution: Restore IP Addresses

Let's solve the Restore IP Addresses problem using the Backtracking pattern.

We'll cover the following

Statement

Given that a string, s, contains digits, return a list of all possible valid IP addresses that can be obtained from the string.

Note: The order in which IP addresses are placed in the list is not important.

A valid IP address is made up of four numbers separated by dots ., for example, 255.255.255.123255.255.255.123. Each number falls between 00 and 255255 (including 00 and 255255), and none of them can have leading zeros.

Constraints:

  • The input string s consists of digits only.

  • 4≤4 \leq s.length ≤12\leq 12

Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach would be to check all possible positions of the dots. To place these dots, we initially have 1111 places, then 1010 places for the second dot, 99 places for the third dot, and so on. So, in the worst case, we would need to perform 11×10×9=99011 \times 10 \times 9 = 990 validations.

After placing the dots, each resulting substring between the dots must be validated as a valid number between 00 and 255255 (inclusive) and must not have leading zeros.

Overall, this approach has a time complexity of O(n3)O(n^3) due to the three nested loops required to place the dots. The space complexity is O(1)O(1), because we’re not storing any additional data structures.

Optimized approach using backtracking

To optimize the worst case scenario mentioned in the naive approach, we’ll use backtracking along with constraint checking.

Constraint checking: The idea behind this concept is that once we’ve placed a dot, we only have three possible positions for the next dot—after one digit, after two digits, or after three digits.

This constraint helps reduce the number of combinations we need to consider. Instead of validating 990990 combinations, we only have to check 3×3×3=273 \times 3 \times 3 = 27 combinations.

Let’s see how we’ll implement an algorithm that uses the backtracking pattern to find all possible combinations of valid IP addresses.

We will implement the backtrack function that takes the position of the previously placed dot, prevDot, and the number of dots, dots, to place them as arguments:

  • Iterate over the three available slots, currDot, to place a dot.

  • Check if the current segment from the previous dot to the current one is valid:

    • If yes, place the dot and add the current segment to our segments list.

      • Check if all three dots are placed.

        • If yes, concatenate the segments list into a string and add the ip string to the result list.

        • If not, proceed to place the next dots backtrack(currDot, dots - 1).

      • Remove the last dot to backtrack.

The following slides represents the algorithm described above in more detail:

Let’s look at the code for this solution below.

import java.util.*;
class RestoreIPAddress {
    static int n;
    static String s;
    static LinkedList <String> segments;
    static ArrayList <String> result;
    public static boolean valid(String segment) {
        int m = segment.length(); 
        if (m > 3) 
            return false;
        return (segment.charAt(0) != '0') ? (Integer.valueOf(segment) <= 255) : (m == 1);
    }
    // this function will append the current list of segments to the list of results.
    public static void updateSegment(int currDot) {
        String segment = s.substring(currDot + 1, n);
        if (valid(segment)) { 
            segments.add(segment); 
        
            String ip = String.join(".", segments);
            result.add(ip);
            segments.removeLast();
        }
    }
    public static void backtrack(int prevDot, int dots) {
        int maxPos = Math.min(n - 1, prevDot + 4);
        for (int currDot = prevDot + 1; currDot < maxPos; currDot++) {
            String segment = s.substring(prevDot + 1, currDot + 1);
            if (valid(segment)) {
                segments.add(segment); 
                if (dots - 1 == 0)
                    updateSegment(currDot);
                else
                    backtrack(currDot, dots - 1);
                segments.removeLast(); 
            }
        }
    }
    public static List <String> restoreIpAddresses(String str) {
        n = str.length();
        s = str;
        result = new ArrayList < String > ();
        segments = new LinkedList < String > ();
        backtrack(-1, 3);
        return result;
    }
    public static void main(String[] args) {
        String[] inputs = {
            "0000",
            "25525511135",
            "12121212",
            "113242124",
            "199219239",
            "121212",
            "25525511335"
        };
        for (int i = 0; i < inputs.length; i++) {
            List < String > result = restoreIpAddresses(inputs[i]);
            System.out.print(i + 1);
            System.out.println(".\tInput Addresses: " + inputs[i]);
            System.out.println("\n\tPossible valid IP Addresses are: " + result);
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Restore IP Addresses

Solution summary

Let’s summarize the optimal solution proposed above:

Place each dot after a gap of one digit. Start from the last segment and check whether it is a valid segment. If it is TRUE, then add this segment to the segments list and backtrack to place the dot to complete the previous segments. Recursively call the backtrack function to make all possible valid IP addresses.

Time complexity

The time complexity is O(1)O(1), since we only have to check 3×3×3=273 \times 3 \times 3 = 27 combinations.

Space complexity

Space complexity is also constant, since we can have 1919 valid IP addresses at most.

Additional thoughts

The relationship between the length of the input string and all possible IP addresses that can be generated from the input string can be visualized in the graph below:

The maximum number of IP addresses that can be generated from a string of length 88 is 1919. Any IP address of a length less than 88 will have fewer valid IP address combinations.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.