Regular Expression Matching — The Wildcard Stamp

Boss 11: The Wildcard Stamp

The dungeon finale, and it's the one with a reputation. LeetCode 10, the regex boss, the problem interviewers save for the end of a loop to see who flinches. Here's the secret after ten bosses in this dungeon: it's just another table. Two strings, two axes of prefixes, one transition with a twist. The twist has a name — the star — and the only genuinely new idea in the whole fight is that the star reads backward.

Everything else you already own.

The story

The border checkpoint at the edge of the dungeon. Travelers queue up, each clutching an entry permit — a plain string of letters. You hold the rulebook, and today's rule is a pattern of stamps.

Most stamps are plain letters: the permit must show exactly that letter at that spot. A dot stamp . is the relaxed officer's stamp: any single letter is fine here, just show me something. And then there's the star stamp *, the strange one. It means nothing by itself. It modifies the stamp before it: "that letter, repeated as many times as you like — including zero times."

So the rule c*a*b reads: any number of c's (maybe none), then any number of a's (maybe none), then exactly one b. The permit aab? Zero c's, two a's, one b. Stamp it. Approved.

The catch: the match must cover the entire permit against the entire rule. No skipping the permit's tail, no ignoring leftover stamps. All or nothing.

The problem, dressed up properly

Given a string s and a pattern p, implement regular expression matching where . matches any single character and * matches zero or more of the preceding element. The match must cover the entire input string, not a substring.

LeetCode 10, "Regular Expression Matching". Hard-rated, famously so, and about to be a Tuesday.

The naive attempt

Match recursively, branching whenever a star shows up:

def is_match(s, p):
    def walk(i, j):
        if j == len(p):
            return i == len(s)
        first = i < len(s) and p[j] in (s[i], '.')
        if j + 1 < len(p) and p[j + 1] == '*':
            return (walk(i, j + 2)              # star spends zero copies
                    or (first and walk(i + 1, j)))  # star eats one more char
        return first and walk(i + 1, j + 1)
    return walk(0, 0)

Correct, and it works fine until a traveler hands you aaaaaaaab against the rule a*a*a*a*b. Every a* can claim zero, one, two... of the a's, and the branches multiply into an exponential tree, most of it re-checking the same leftover suffixes over and over.

But look at the state: just (i, j). Two indices, at most m by n distinct pairs. Memoize on that pair and the tree collapses. And once the state is two indices into two strings, you know this dungeon's opening move by heart: make them axes and build the table.

The weapon: the prefix table, one last time

Define dp[i][j] = True if the first i characters of the permit s match the first j stamps of the rule p. Same axes-as-prefixes shape as the Two Diaries, same one-cell-answers-one-honest-question discipline as everything since.

Base cases first, and this boss actually punishes sloppiness here. dp[0][0] is True: empty permit, empty rule, trivially matched. Column 0 below that is all False — a non-empty permit can't match an empty rule. But row 0 is not all False. An empty permit can still match a*, or a*b*c*, because every starred group can choose zero copies. So walk row 0 and let each * reach two columns back: dp[0][j] = dp[0][j-2] when p[j-1] is a star.

Now the transitions, for the general cell. Remember dp index j means "first j stamps", so the current stamp is p[j-1] and the one before it is p[j-2].

Plain letter or dot. The current stamp must consume the permit's current character. If p[j-1] equals s[i-1], or p[j-1] is ., then both sides shrink by one and the answer comes from the diagonal: dp[i][j] = dp[i-1][j-1]. Otherwise False.

Star. Here's the backward read. A * at stamp position j has no meaning alone — it's welded to p[j-2], and together they form one unit: "p[j-2], zero or more times." Two options, OR-ed:

• Zero copies. The whole x* unit vanishes. Skip both stamps: dp[i][j] = dp[i][j-2]. That's why the transition looks two columns left — you're jumping over the star and its letter in one hop.
• One more copy. If the permit's current character s[i-1] matches the starred letter (equal to p[j-2], or p[j-2] is .), the star eats it and stays armed: dp[i][j] = dp[i-1][j]. Permit shrinks, rule doesn't, because the star can keep eating.

def is_match(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
 
    for j in range(1, n + 1):            # empty permit vs rule prefixes
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]      # x* can mean zero copies
 
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[i][j] = dp[i][j - 2]                       # zero copies
                if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j]       # one more
            elif p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]                   # plain stamp
    return dp[m][n]

The exponential branching tree, flattened into m·n cells that each get computed once.

Watching it work

The classic: permit s = "aab", rule p = "c*a*b". Rows are permit prefixes, columns are rule prefixes.

            ""    c    c*   c*a  c*a*  c*a*b
     ""      T    F    T    F    T     F
     a       F    F    F    T    T     F
     aa      F    F    F    F    T     F
     aab     F    F    F    F    F     T

The rows that matter:

• Row "" : c* is True (zero c's), and c*a* is True (zero of each) — each star reaching two columns back to a True. The rulebook can dissolve to nothing.
• Row "a", column c*a: diagonal from the True at ("", c*), chars a and a agree. The first a is consumed by the plain-ish path.
• Row "aa", column c*a*: the star's one-more branch. s char is a, starred letter is a, and the cell above at ("a", c*a*) is True. The star eats a second a and stays armed.
• Row "aab", column c*a*b: plain b stamp, diagonal from the True at ("aa", c*a*). Full permit, full rule, both exhausted together.

dp[3][5] is True. Stamp the permit. Boss staggers.

Gotchas

1. A lazy row 0. Initializing row 0 as [True, False, False, ...] fails the very first hidden test: s = "", p = "a*" must be True. Every starred pair in the rule can evaporate, so row 0 has scattered Trues wherever chains like a*b*c* reach back to dp[0][0]. Skip the row-0 loop and the whole table inherits the mistake.

2. Off-by-one soup around p[j-2]. dp indices count prefix lengths, string indices count positions. The current stamp is p[j-1], the starred letter is p[j-2], and the zero-copy jump is dp[i][j-2]. Mix "table j" with "string j" once and you'll compare the star against itself or walk off the front of the pattern. Write the two mappings as comments before writing the transition.

3. Treating * as its own token. The star is not a stamp, it's a modifier — it has no meaning without the letter before it. If your code ever asks "does s[i-1] match *?", the model is already broken. Valid patterns never start with *, and every star's letter lives at p[j-2]. This is exactly why the transition reads backward.

4. Matching a substring instead of the whole permit. The answer lives at dp[m][n], both strings fully consumed — not "did any cell in the last row light up". s = "aab" against p = "aa" matches a prefix beautifully and must still return False. Full permit, full rule, no leftovers. The checkpoint does not do partial credit.

Complexity

An m+1 by n+1 table, each cell filled by at most two O(1) lookups.

Time: O(m·n). Space: O(m·n). Two rows suffice if you want O(n) space, since every transition reads the current row and the one above.

Boss down. Dungeon cleared.

The star stamp hits the last permit, the gate swings open, and Dungeon 16 goes quiet behind you. Eleven bosses, one weapon the whole way through — the table — and eleven different reasons to build one:

• Grid paths (Boss 1, One-Way City): cells as literal places, answers flowing from two neighbors
• Prefix axes and max (Boss 2, Two Diaries): two strings become two axes, the diagonal carries agreement
• State machines as a dimension (Boss 3, Collector's Cooldown): holding, cooling, free — states multiply the table instead of the work
• Loop order as a hidden axis (Boss 4, Token Booth): combinations vs permutations decided by which loop wraps which
• Reshaping the question (Boss 5, Tug of War): signs and targets rewritten into a subset-sum the table already knows
• OR-tables and degrees of freedom (Boss 6, Braided Rope): True/False cells, two strands feeding one weave
• DP on a DAG (Boss 7, Terrace Climb): memoized DFS when the grid's arrows, not its walls, define the order
• Counting tables (Boss 8, Scrapbook Cutouts): cells that tally how many ways instead of whether
• The three-move classic (Boss 9, Proofreader's Bill): insert, delete, replace — edit distance and its diagonal heart
• Interval DP (Boss 10, Carnival Pop): axes as ranges, and the trick of deciding what happens last, first
• Backward-reading wildcards (Boss 11, Wildcard Stamp): a star welded to its letter, zero-or-more as two OR-ed branches

The through-line: 2-D DP was never about grids. It was about choosing two axes that make subproblems overlap — prefixes, states, intervals, capacities — so that an exponential tree of choices folds into a rectangle of cells you fill exactly once. Pick the right axes and the transition almost writes itself. Every boss here was really an axes-choosing puzzle with a story wrapped around it.

Next dungeon: Bit Manipulation. Dungeon 17 speaks the machine's own language: XOR tricks that find the lonely element in one pass, shifts that multiply and divide for free, bit-counting identities, and problems where an entire visited-set collapses from O(n) space into a single integer. After sixteen dungeons of building structures, the last stretch is about needing almost none. See you at the gate.