0247MediumStringBacktracking

Panel Address Splits

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A relay panel is identified by four numeric fields joined with -, for example 12-7-0-240. Each field is held in a single byte, so its value runs from 0 to 255, and each field is written in its shortest form: either the single digit 0, or a number whose first digit is not 0.

A technician copied a panel address down without the separators, leaving only digits, a string of decimal digits.

Return every panel address that produces exactly digits once its three separators are dropped, in any order. Return an empty list when no address produces it.

Examples

Example 1

Input: digits = "01203"
Output: ["0-12-0-3", "0-1-20-3"]

Both addresses reproduce 01203 when the separators come out, and each of their fields is either a lone 0 or a number that does not open with 0.

Example 2

Input: digits = "10203"
Output: ["10-2-0-3", "1-0-20-3"]

Every field shown lies between 0 and 255 and none opens with a 0 it does not need, so both addresses qualify.

Example 3

Input: digits = "9"
Output: []

Four fields need at least four digits between them, and only one digit was copied down.

Constraints

1 <= digits.length <= 20
digits consists of decimal digits only

The values you return may be in any order.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def panel_addresses(digits: str) -> list[str]:

Java

public List<String> panelAddresses(String digits)

The intended approach

Time O(1) on the declared bound: a string of at most 20 digits admits at most 3^4 = 81 four-field layouts, and each is checked in constant time.Space O(1) working memory beyond the list of addresses returned.

Lay the fields down left to right, trying a one, two or three digit chunk for each and abandoning a chunk that opens with a 0 it does not need or that reads above 255. A branch is recorded only when the fourth field lands exactly on the end of the string, and each field is taken back off before the next width is tried.

Pythonentry point: panel_addresses

def panel_addresses(digits):
    total = len(digits)
    found = []
    fields = []

    def place(at):
        if len(fields) == 4:
            if at == total:
                found.append("-".join(fields))
            return
        for width in (1, 2, 3):
            if at + width > total:
                break
            chunk = digits[at:at + width]
            if width > 1 and chunk[0] == "0":
                continue
            if int(chunk) > 255:
                continue
            fields.append(chunk)
            place(at + width)
            fields.pop()

    place(0)
    return found

The obvious version

Choose the three separator positions with three nested loops, cut the string at them and keep the cut when all four pieces pass the field rules. O(L^3) for a string of length L.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_panel_addresses(digits):
    total = len(digits)

    def usable(chunk):
        if len(chunk) < 1 or len(chunk) > 3:
            return False
        if len(chunk) > 1 and chunk[0] == "0":
            return False
        return int(chunk) <= 255

    out = []
    for first in range(1, total):
        for second in range(first + 1, total):
            for third in range(second + 1, total):
                parts = [digits[:first], digits[first:second],
                         digits[second:third], digits[third:]]
                if all(usable(part) for part in parts):
                    out.append("-".join(parts))
    return out

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in