Restore IP Addresses

Medium Recursion & Backtracking Choice per Position Original on LeetCode

Restore IP Addresses is a medium recursion & backtracking problem solved with the choice per position pattern. The best approach, optimal (backtracking with pruning), runs in O(1) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every dot placement) up.

Problem

A valid IPv4 address is four integers separated by single dots. Each integer is between 0 and 255 and is written without leading zeros, so "10.0.7.255" is valid while "10.07.1.1" and "10.256.1.1" are not.

You are given a string s made only of digits. Insert exactly three dots into s (without reordering, adding or removing any digit) and return every valid IP address that can be formed. The addresses may be returned in any order.

Examples

Example 1

Input
s = "2550255"
Output
["2.5.50.255", "2.55.0.255", "25.5.0.255", "25.50.2.55", "25.50.25.5", "255.0.2.55", "255.0.25.5"]
Why
Every way to cut the seven digits into four parts that are each 0–255 with no leading zero.

Example 2

Input
s = "10023"
Output
["1.0.0.23", "10.0.2.3"]
Why
Splits like "1.00.2.3" or "100.2.3" are rejected: a part may not have a leading zero, and there must be four parts.

Example 3

Input
s = "0000"
Output
["0.0.0.0"]
Why
A single 0 is a valid part, so the only address uses four of them.

Constraints

  • 1 <= s.length <= 20
  • s contains digits only.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every dot placement)O(1)O(1)
Optimal (backtracking with pruning)O(1)O(1)

1Brute force (try every dot placement)

TimeO(1)At most 3 × 3 × 3 = 27 splits, each checked on at most 12 characters.
SpaceO(1)Apart from the output, only the four substrings of the current split.

Choose the lengths of the first three parts (each 1 to 3); the fourth part is whatever remains. Check all four parts and keep the address if every part is valid.

  1. Loop a, b, c over 1..3 (lengths of parts 1–3).
  2. The fourth part has length n - a - b - c; skip unless it is 1..3.
  3. Cut the four substrings and validate each one.
  4. If all four are valid, join them with dots and add to the answer.
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> out = new ArrayList<>();
        int n = s.length();
        for (int a = 1; a <= 3; a++)
            for (int b = 1; b <= 3; b++)
                for (int c = 1; c <= 3; c++) {
                    int d = n - a - b - c;
                    if (d < 1 || d > 3) continue;
                    String p1 = s.substring(0, a), p2 = s.substring(a, a + b);
                    String p3 = s.substring(a + b, a + b + c), p4 = s.substring(a + b + c);
                    if (ok(p1) && ok(p2) && ok(p3) && ok(p4)) out.add(p1 + "." + p2 + "." + p3 + "." + p4);
                }
        return out;
    }

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

2Optimal (backtracking with pruning)

TimeO(1)The recursion tree has at most 3⁴ = 81 leaves, and pruning cuts most of them.
SpaceO(1)Recursion depth is 4 and the current path holds 4 parts.

Build the address one part at a time. From position start, try a part of length 1, 2 or 3; keep it only if it is a valid part, then recurse for the next part. Prune as soon as the remaining digits are too few or too many for the remaining parts (each part needs 1 to 3 digits).

  1. If the length is outside 4..12, return an empty list.
  2. dfs(start, parts): if 4 parts are chosen, record the address when start == n.
  3. Let left = 4 - parts. If n - start < left or n - start > 3 * left, return.
  4. Try len = 1..3: stop at a leading zero for len > 1 or a value above 255; otherwise push the part, recurse, pop.
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> out = new ArrayList<>();
        if (s.length() < 4 || s.length() > 12) return out;
        dfs(s, 0, new ArrayList<>(), out);
        return out;
    }

    private void dfs(String s, int start, List<String> parts, List<String> out) {
        int n = s.length(), left = 4 - parts.size();
        if (left == 0) {
            if (start == n) out.add(String.join(".", parts));
            return;
        }
        if (n - start < left || n - start > 3 * left) return;
        int val = 0;
        for (int len = 1; len <= 3 && start + len <= n; len++) {
            if (len > 1 && s.charAt(start) == '0') break;
            val = val * 10 + (s.charAt(start + len - 1) - '0');
            if (val > 255) break;
            parts.add(s.substring(start, start + len));
            dfs(s, start + len, parts, out);
            parts.remove(parts.size() - 1);
        }
    }
}

Edge cases to test

  • Fewer than 4 or more than 12 digits: no answer
  • Zeros: "0" is a valid part, but "01" or "00" are not
  • Parts above 255, like "256"
  • A string of all zeros, like "0000"

Hints

Hint 1

An address has exactly four parts, each one to three digits long. How many ways can you place three dots?

Hint 2

A part is valid when it is "0" or starts with a non-zero digit, and its value is at most 255.

Hint 3

Build the parts left to right and stop early when the digits left cannot fill the remaining parts.

FAQ

What is the best time complexity for Restore IP Addresses?

Optimal (backtracking with pruning) runs in O(1) time and O(1) extra space. The recursion tree has at most 3⁴ = 81 leaves, and pruning cuts most of them.

Which pattern does Restore IP Addresses use?

It is a recursion & backtracking problem that uses the choice per position pattern. Other problems with the same pattern: Letter Combinations of a Phone Number, Confusing Number II, Strobogrammatic Number II.

Is there a brute force solution for Restore IP Addresses?

Yes. Brute force (try every dot placement) takes O(1) time and O(1) space. Choose the lengths of the first three parts (each 1 to 3); the fourth part is whatever remains.

Which edge cases should I test for Restore IP Addresses?

Fewer than 4 or more than 12 digits: no answer; Zeros: "0" is a valid part, but "01" or "00" are not; Parts above 255, like "256"; A string of all zeros, like "0000".