Recall mask

A recall notice is written with wildcards, and a star can be spent in many places. The greedy reading is wrong, and so is the exponential fix.

The problem

A paint plant stamps every tin with a batch code of lowercase letters and digits. When a batch goes bad the plant issues a recall notice: a mask over the same alphabet plus two wildcards:

• ? stands for exactly one character;
• * stands for any run of characters, including none.

A tin is recalled when the mask covers its code from first character to last — the whole code, not a piece. Decide whether one tin is recalled.

Input. batch — the code on the tin. mask — the recall notice.

Output. True if the mask covers the whole code, else False.

Example.

batch = "kx4218", mask = "kx*8"    ->  True
batch = "kx4218", mask = "kx?8"    ->  False

The star covers 421. The ? covers exactly one character, and four sit between kx and the 8.

A second example, where the star has to give characters back:

batch = "kx4218", mask = "*18"     ->  True
batch = "kx4218", mask = "*x*1*"   ->  True
batch = "kx4218", mask = "kx*9"    ->  False

A star that swallows the code to the end leaves nothing for the 18, so the first line looks false to a greedy reader: the star has to settle for kx42. The last line fails because a star covers characters but cannot turn the code's final 8 into the notice's 9.

Constraints.

• 0 <= len(batch) <= 300, lowercase letters and digits
• 0 <= len(mask) <= 300, those plus ? and *
• an empty mask covers only an empty code; a mask of stars covers every code

Hints

Approach

Brute force

Try every way of dividing the code among the stars: about C(n + s, s) divisions for s stars over n characters. A five-star notice against a 300-character code gives more than 2 × 10¹⁰, each then verified in O(n).

The insight

The answer depends on two numbers — how much code is left and how much mask is left — so a cursor pair is the whole state, and no pair is worked out twice.

Two branches at a star and one everywhere else makes a tree that can be exponential, but there are only (n + 1) × (m + 1) cursor pairs — at most 90,601 here. The answer at (i, j) depends on the two suffixes alone, never on the path that reached it, which is the precondition memoisation needs.

Algorithm

1. covers(i, j) — does batch[i:] match mask[j:]?
2. Mask spent: the answer is whether the code is spent too.
3. *: the star ends here, covers(i, j + 1); or it takes one more character, covers(i + 1, j).
4. Code spent, mask not: False — only a star covers nothing.
5. ? or a matching literal: covers(i + 1, j + 1). Anything else: False.
6. Cache every (i, j).

Complexity

Time O(n · m) — one evaluation per cursor pair, O(1) work in each. Space O(n · m) for the cache, plus O(n + m) frames of depth. Depth is why a much longer code wants this recurrence filled in as a table instead: Python gives up near 1,000 frames.

Solution

"""Recall mask — wildcard cover by recursion on two cursors, with a cache."""
from functools import lru_cache


def solve(batch, mask):
    n, m = len(batch), len(mask)

    @lru_cache(maxsize=None)
    def covers(i, j):
        # invariant: the answer depends only on the suffixes batch[i:] and
        # mask[j:], never on how the cursors got here — which is what makes
        # (i, j) a sound cache key.
        if j == m:
            return i == n                       # mask spent: only an empty tail fits
        if mask[j] == "*":
            if covers(i, j + 1):                # the star ends here
                return True
            return i < n and covers(i + 1, j)   # or takes one more, then reconsiders
        if i == n:
            return False                        # only a star can cover nothing
        if mask[j] == "?" or mask[j] == batch[i]:
            return covers(i + 1, j + 1)
        return False

    answer = covers(0, 0)
    covers.cache_clear()
    return answer

TESTS = [
    (("kx4218", "kx*8"), True),
    (("kx4218", "kx?8"), False),
    (("kx4218", "*18"), True),          # the star must give the "18" back
    (("kx4218", "*x*1*"), True),
    (("kx4218", "kx*9"), False),
    (("kx", "kx*"), True),              # a star may cover nothing at all
    (("", "***"), True),
    (("", ""), True),
    (("a", ""), False),
    (("a" * 60, "*a*a*a*a*b"), False),  # exponential without the cache
]

Pitfalls

• Reading * as "one or more". The notice kx* misses the tin kx, the shortest code in the family it was written to recall.
• Letting the star run to the end and never backing off. *18 against kx4218 comes back False, because the star ate the 18 the mask still needed; the second branch is what gives characters back.
• Dropping the cache. *a*a*a*a*b against three hundred as re-derives the same cursor pairs for minutes; cached, it is a few thousand questions.

Variants

• Mirror panels — a string carved up by recursion too, but each piece is judged on its own, with nothing remembered.
• The recursion framework — naming the state is what tells you the cache key is (i, j).