Program to generate all possible valid IP addresses from given string

The problem, simply

An IP address is four numbers joined by dots, like 192.168.1.1. Each number is from 0 to 255, and a number may not start with 0 unless it is just 0. So 1.0.20.3 is fine, but 1.02.0.3 and 1.0.256.3 are not.

You get a string of digits with no dots. Give back every IP address you can make by putting exactly three dots into it. You may not add, remove or reorder digits.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every place for the three dots. The first dot goes after position i, the second after j, the third after k, with i < j < k. For each choice, check all four parts.

1. Loop i, j and k over all cut points.
2. Cut the four parts and check each: 1 to 3 digits, no leading 0, at most 255.
3. If all four pass, join them with dots and keep the address.

import java.util.*;

class Solution {
    private boolean ok(String p) {
        if (p.isEmpty() || p.length() > 3) return false;
        if (p.length() > 1 && p.charAt(0) == '0') return false;   // no leading zero
        return Integer.parseInt(p) <= 255;
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> out = new ArrayList<>();
        int n = s.length();
        for (int i = 1; i < n; i++)
            for (int j = i + 1; j < n; j++)
                for (int k = j + 1; k < n; k++) {
                    String a = s.substring(0, i), b = s.substring(i, j);
                    String c = s.substring(j, k), d = s.substring(k);
                    if (ok(a) && ok(b) && ok(c) && ok(d)) {
                        out.add(a + "." + b + "." + c + "." + d);
                    }
                }
        return out;
    }
}

How long it takes: about n^3 / 6 ways to place three dots, each checked quickly, so O(n^3). Extra room: the four small part strings, O(n). It keeps trying dots far apart even when a part is clearly longer than 3 digits.

Way 2: the clever way

Cut the ribbon one part at a time with recursion, and stop a branch as soon as it cannot work. Each part has only 3 lengths to try, and there are only 4 parts, so the whole tree has at most 3^4 = 81 bottom ends, no matter what.

1. If 4 parts are cut, keep the address only if no digits are left.
2. If the digits left are fewer than the parts still needed, or more than 3 times that, stop.
3. Try the next part with 1, 2 and 3 digits. Skip it if it starts with 0 (and is longer than one digit) or is above 255.
4. Add the part, go deeper, then remove it again.

import java.util.*;

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> out = new ArrayList<>();
        cut(s, 0, new ArrayList<>(), out);
        return out;
    }

    private void cut(String s, int start, List<String> parts, List<String> out) {
        if (parts.size() == 4) {
            if (start == s.length()) out.add(String.join(".", parts));
            return;
        }
        int left = s.length() - start, need = 4 - parts.size();
        if (left < need || left > need * 3) return;          // cannot fit, stop early

        for (int len = 1; len <= 3 && start + len <= s.length(); len++) {
            String p = s.substring(start, start + len);
            if (len > 1 && p.charAt(0) == '0') break;          // 0 can only stand alone
            if (Integer.parseInt(p) > 255) break;              // longer will be even bigger
            parts.add(p);
            cut(s, start + len, parts, out);
            parts.remove(parts.size() - 1);                    // undo
        }
    }
}

How long it takes: at most 81 bottom ends, each joined in at most 15 characters, so O(3^4), which is a constant, O(1). Extra room: the recursion is 4 levels deep, O(1), not counting the answers.

Watch out for

• Do not stop at 4 parts if digits are left over. 1.0.2.0 from 10203 leaves a 3 behind and is not an answer.
• Integer.parseInt on a long part can overflow. Checking the length is at most 3 first keeps it safe.
• A string longer than 12 or shorter than 4 digits has no answers. The pruning catches this right away.
• The answer may be an empty list. Do not return null.

What interviewers ask next

• Why break instead of continue in the loop? A part that starts with 0 stays bad when you add digits, and a number above 255 only gets bigger. Nothing longer can help.
• How many answers can there be at most? Small. Every address is decided by 3 part lengths of 1 to 3, so at most 27 for one string, and far fewer in practice.
• Validate one IPv4 or IPv6 address instead? Split on dots or colons, then check each part by its own rules (IPv6 parts are 1 to 4 hex digits).
• The same skeleton with a different rule? Splitting a string into words from a dictionary, or into palindromes, uses the exact same "cut a piece, check it, recurse, undo" loop.

Remember this

Grown-up words: cutting the ribbon is partitioning the string, the tree of cuts is a recursion tree, stopping early is pruning, and the whole method is backtracking.