0177MediumArrayHash TableStringDynamic ProgrammingTrieMemoizationBrute-Force Search

Label Splits Into Codes

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 firmware build stamps each module with a short lowercase code, and the label of an assembled unit is the codes of its modules written one after another with nothing in between.

You are given a label label and a catalogue codes of the codes in use, all distinct. Decide whether label could have come off the line: is there a run of catalogue codes whose concatenation is exactly label, using every character of the label and adding none?

A code may be reused as often as needed, and the catalogue may contain codes that go unused. Return true if such a run exists and false otherwise.

Examples

Example 1

Input: label = "portmapper", codes = ["port", "map", "per"]
Output: true

The label breaks into `port`, `map` and `per`, three catalogue codes in a row with nothing left over.

Example 2

Input: label = "gridlockgrid", codes = ["grid", "lock"]
Output: true

`grid` is stamped twice, once at the front and once at the back, which is allowed because codes may repeat.

Example 3

Input: label = "sunflower", codes = ["sun", "flow", "power"]
Output: false

`sun` and `flow` cover the first seven characters and leave `er`, which no code matches, and `power` never lines up anywhere in the label. No run of codes reproduces it.

Constraints

1 <= label.length <= 300
1 <= codes.length <= 1000
1 <= codes[i].length <= 20
label and codes[i] consist of lowercase English letters only
All codes are distinct

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 label_splits(label: str, codes: list[str]) -> bool:

Java

public boolean labelSplits(String label, List<String> codes)

The intended approach

Time O(n * k * L)Space O(n + m)

Work along the label and keep a flag per prefix length saying whether that prefix can be produced. A prefix ending at position `end` works when some catalogue code of length `w` sits in the label just before `end` and the prefix of length `end - w` already works. Only the distinct code lengths need trying, and membership is a set lookup, so each position costs a handful of slices. The flag for the whole label is the answer.

Pythonentry point: label_splits

def label_splits(label, codes):
    # n is the label length, k the number of distinct code lengths and L the
    # longest code, so slicing and hashing each candidate gives O(n * k * L)
    # time. The flags cost O(n) and the catalogue set O(m) total characters.
    catalogue = set(codes)
    widths = sorted({len(code) for code in codes})
    reachable = [False] * (len(label) + 1)
    reachable[0] = True
    for end in range(1, len(label) + 1):
        for width in widths:
            if width > end:
                break
            if reachable[end - width] and label[end - width:end] in catalogue:
                reachable[end] = True
                break
    return reachable[len(label)]

The obvious version

Plain recursive search: from the current position try every catalogue code that matches there and recurse, with no memory of positions already explored. Exponential, but obviously correct.

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_label_splits(label, codes):
    def peel(position):
        if position == len(label):
            return True
        for code in codes:
            if label.startswith(code, position) and peel(position + len(code)):
                return True
        return False

    return peel(0)

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