Smudged Router Label

MediumbacktrackingAlso known as Restore IP Addresses

A repair shop prints a sticker with each device's network address, like 192.168.1.1. The label printer has a fault: it drops every dot. A sticker now just reads 19216811, and the technician has to work out which addresses it could have been.

A valid address is four numbers separated by dots. Each number is from 0 to 255 and is written without leading zeros, so 0 is fine but 01 and 00 are not.

Your task

Write possibleAddresses(label). label is a string of digits. Return every valid address that becomes label when its three dots are removed, written with the dots, like "192.168.1.1".

Use every digit, in the given order. Return the addresses in any order, each once. If none is possible, return an empty list.

possibleAddresses(label: string) → string[] Any order of the returned list is accepted.

Examples

Example 1

Input

label = "19216811"

Output

["1.92.168.11", "19.2.168.11", "19.21.68.11", "19.216.8.11", "19.216.81.1", "192.1.68.11", "192.16.8.11", "192.16.81.1", "192.168.1.1"]

Why

Eight digits split into four numbers. 192.168.1.1 is the address the printer started from, but the sticker cannot tell it apart from the others: 19.216.81.1 is also four numbers from 0 to 255. Something like 1.921.68.11 does not, because 921 is over 255.

Example 2

Input

label = "10203"

Output

["1.0.20.3", "10.2.0.3"]

Why

Five digits in four numbers means exactly one number has two digits. 10.2.0.3 and 1.0.20.3 work. 1.02.0.3 and 1.0.2.03 fail, because a number cannot start with 0 unless it is just 0.

Constraints

0 ≤ label.length ≤ 20
label contains only the digits 0 to 9.
Addresses may be returned in any order.

Start with brute force

There are n − 1 gaps between digits. Try every way to choose 3 of them for the dots and check the four pieces. For a 12-digit label that is only 165 choices, so this is not slow at this size; its weakness is that it is rigid and wasteful.

It builds and checks splits whose first piece is 1921 or 05, which were hopeless from the first cut, and the three nested loops are hard-wired to four parts. Building the address piece by piece and rejecting a bad piece the moment it appears does less work and works for any number of parts.

Hints

0 of 4 shown

Hint 1
Look at "10203". The first number of the address can only be 1, 2 or 3 digits long. Which of 1, 10 and 102 are allowed as a first number?
Hint 2
Once you fix the first number, what is left is the same puzzle on a shorter string, with three numbers still to place. That is a recursive structure.
Hint 3
Write place(start), which tries a piece of length 1, 2 or 3 starting at start. Skip a piece if it runs past the end, has a leading zero, or is over 255. After four pieces, keep the address only if every digit has been used.
Hint 4
Add the piece to a list of parts, recurse on start + length, then remove it. A piece that starts with 0 or is over 255 only gets worse when longer, so you can stop trying longer pieces. A label longer than 12 digits can be rejected at once.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

An address is four choices in a row: how many digits the next number takes, 1, 2 or 3. Each choice either breaks a rule right away or leaves a smaller version of the same puzzle, so recursion with three branches per level fits.

Trace "10203":

First piece 1. Rest 0203. Second piece 0 (the only option: 02 has a leading zero). Rest 203.
- Third piece 2, fourth piece must be 03: leading zero, rejected.
- Third piece 20, fourth 3: record 1.0.20.3.
- Third piece 203 leaves nothing for the fourth.
First piece 10. Rest 203: pieces 2, 0, 3 give 10.2.0.3. Longer pieces leave too few digits.
First piece 102. Rest 03: second piece 0, third 3, and no digit is left for the fourth. Dead end.

Two addresses. Watch the leading-zero rule: 0 alone is allowed, so check "longer than 1 digit and starts with 0", not "starts with 0".

Reference solution

function possibleAddresses(label) {
  const results = [];
  const parts = [];
  function place(start) {
    if (parts.length === 4) {
      if (start === label.length) results.push(parts.join('.'));
      return;
    }
    for (let len = 1; len <= 3; len++) {
      if (start + len > label.length) break;
      const piece = label.slice(start, start + len);
      if (len > 1 && piece[0] === '0') break; // no leading zeros
      if (Number(piece) > 255) break;         // longer is bigger still
      parts.push(piece);
      place(start + len);
      parts.pop();
    }
  }
  if (label.length <= 12) place(0); // 4 parts of at most 3 digits
  return results;
}

def possible_addresses(label):
    results = []
    parts = []
 
    def place(start):
        if len(parts) == 4:
            if start == len(label):    # all digits used
                results.append('.'.join(parts))
            return
        for length in (1, 2, 3):
            if start + length > len(label):
                break
            piece = label[start:start + length]
            if length > 1 and piece[0] == '0':
                break                  # no leading zeros
            if int(piece) > 255:
                break                  # longer pieces are bigger still
            parts.append(piece)
            place(start + length)
            parts.pop()
 
    if len(label) <= 12:               # 4 parts of at most 3 digits
        place(0)
    return results

TimeO(1)Labels longer than 12 digits are rejected at once, and otherwise there are at most 3⁴ = 81 ways to choose the piece lengths, each checked in constant time.

SpaceO(1)The recursion is at most 4 levels deep, and there are at most a few dozen answers.

Learn the idea: Backtracking Strings

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code