0181HardStringDynamic ProgrammingRecursion

Mask Matches The Whole Code

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 parts catalogue lets a technician look up stock with a mask instead of an exact serial. You are given a serial code of lowercase letters and a mask mask, and you have to decide whether the mask describes that serial.

Read mask left to right as a run of items. An item is one lowercase letter, which stands for that letter alone, or '.', which stands for any one letter. Writing '*' straight after an item says that the item is used some number of times over, possibly not at all. Every '*' in mask is guaranteed to follow an item.

Return true when the items account for code from its first letter through its last, with nothing left over on either side, and false otherwise. Covering a leading chunk of code is not enough.

Examples

Example 1

Input: code = "harp", mask = "hz*arp"
Output: true

The item z is used zero times over, so the mask boils down to h, a, r, p, which lines up with the serial.

Example 2

Input: code = "harp", mask = "h.r."
Output: true

Each dot stands in for one letter, so the four items cover all four letters of the serial.

Example 3

Input: code = "harp", mask = "har"
Output: false

The items only reach the first three letters and nothing accounts for the trailing p.

Constraints

1 <= code.length <= 20
1 <= mask.length <= 20
code contains only lowercase English letters.
mask contains only lowercase English letters, '.', and '*'.
Every appearance of '*' is preceded by a valid item.

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 mask_matches(code: str, mask: str) -> bool:

Java

public boolean maskMatches(String code, String mask)

The intended approach

Time O(len(code) * len(mask))Space O(len(code) * len(mask))

Ask the suffix question: can `mask` from position j onward account for `code` from position i onward? A plain item forces one letter and steps both forward. A repeated item either steps over the item and its star without spending a letter, or consumes one matching letter and stays on the same item, which is what lets one item stretch. Filling the table from the back means both of those answers are already known.

Pythonentry point: mask_matches

def mask_matches(code, mask):
    # table[i][j] answers: does mask[j:] describe code[i:] exactly?
    # Filled from the back so a repeat item can look at its own row.
    # Time O(len(code) * len(mask)), space O(len(code) * len(mask)).
    n, m = len(code), len(mask)
    table = [[False] * (m + 1) for _ in range(n + 1)]
    table[n][m] = True
    for i in range(n, -1, -1):
        for j in range(m - 1, -1, -1):
            here = i < n and (mask[j] == "." or mask[j] == code[i])
            if j + 1 < m and mask[j + 1] == "*":
                # skip the repeat entirely, or spend one character on it
                table[i][j] = table[i][j + 2] or (here and table[i + 1][j])
            else:
                table[i][j] = here and table[i + 1][j + 1]
    return table[0][0]

The obvious version

Split the mask into items, then spell out every concrete pattern the mask could stand for by expanding each repeated item into 0, 1, 2, ... copies up to the serial length. Accept if any spelled pattern has the same length as the serial and agrees letter by letter, with dots free. Exponential in the number of repeated items.

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_mask_matches(code, mask):
    items = []
    j = 0
    while j < len(mask):
        repeat = j + 1 < len(mask) and mask[j + 1] == "*"
        items.append((mask[j], repeat))
        j += 2 if repeat else 1

    limit = len(code)
    spelled = [""]
    for symbol, repeat in items:
        grown = []
        for prefix in spelled:
            if repeat:
                for times in range(limit - len(prefix) + 1):
                    grown.append(prefix + symbol * times)
            else:
                grown.append(prefix + symbol)
        spelled = [text for text in grown if len(text) <= limit]

    for text in spelled:
        if len(text) != limit:
            continue
        if all(a == "." or a == b for a, b in zip(text, code)):
            return True
    return False

How this problem was checked

Reference solution executed against 17 test cases — 17 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