Regular Expression Matching

A greedy scan breaks at * because the pattern can take two legal futures: skip the quantified element, or consume one matching character and keep the same pattern position. The reliable model is reachability between two suffix indices.

Read the matching contract first

This problem uses a deliberately restricted pattern language:

• A literal character matches itself.
• . matches exactly one arbitrary character.
• * applies to the immediately preceding element and matches zero or more occurrences of that element.
• The match must consume all of s, not merely a prefix.
• Every * has a valid preceding element.

The pattern does not include groups, alternation, escapes, anchors, or the broader semantics of a full regular-expression engine. Do not reach for Python's re module here. The interview problem has a smaller language and a clean recursive structure.

Let:

• n = len(s)
• m = len(p)

The answer is whether the entire suffix s[0:] matches the entire suffix p[0:].

The useful direction is immediate:

Memoize whether each pair of suffixes s[i:] and p[j:] matches. There are at most (n + 1)(m + 1) such pairs, so the dynamic program runs in O(nm) time.

The difficulty is deriving the transitions without accidentally changing the meaning of *.

Why a greedy scan fails at *

Without *, matching is deterministic. At pattern index j, either:

1. p[j] is compatible with s[i], so consume both; or
2. the characters are incompatible, so fail.

Compatibility means:

p[j] == s[i] or p[j] == '.'

A star introduces a choice. Consider:

s = "aab"
p = "c*a*b"

At c*, the pattern may match zero c characters and move past c*. It must not consume a character from s, because the next text character is a, not c.

At a*, the pattern may:

• match zero a characters and move to b; or
• match one a, remain at a*, and possibly match another a.

Those are the only semantic choices for zero-or-more:

1. Skip the quantified element entirely.
2. Consume one compatible text character and keep the quantified element available.

A greedy algorithm might repeatedly consume while the current character matches. That is unsafe. It can consume too much and leave the pattern suffix unable to match. It can also commit to repetition when the valid solution requires zero occurrences.

For example, suppose a star can match the current character, but the remaining pattern must consume that character later in a different way. Greedy repetition has destroyed a possible path. The pattern is a branching process, not a single forward scan.

The natural brute-force recursion explores both branches. Its weakness is repeated work. Different choices can lead back to the same pair (i, j), meaning the same two suffixes are solved repeatedly. Memoization turns that recursive derivation into dynamic programming.

Define the two-index suffix state

Define:

match(i, j) = whether s[i:] matches p[j:]

This state is semantic. The two dimensions are not arbitrary table coordinates:

• i records how much text has been consumed.
• j records how much pattern has been consumed.

Most importantly, i and j do not always advance together. A star can advance the pattern without consuming text, or consume text without advancing the pattern. One coordinate can move while the other waits.

That is the structural signal for two-dimensional dynamic programming.

Base case: pattern exhausted

If j == m, no pattern remains. A full match exists only if no text remains:

match(i, m) = (i == n)

This condition enforces full-string matching. If the pattern has been consumed while s[i:] still contains characters, the result is false.

The common mistake is to return true merely because the pattern ended. That accepts a matched prefix, such as treating "a" as a match for "aa".

Empty text

When i == n, the text suffix is empty. A remaining pattern can match it only if the remaining pattern consists entirely of element-star pairs:

a*b*c*

Each pair can disappear by taking its zero-occurrence branch.

Do not need a separate shortcut for this case. If the recurrence is correct, it handles empty text naturally:

match(n, j) -> match(n, j + 2)

whenever p[j + 1] == '*'.

First-character compatibility

At a non-exhausted text suffix, define:

first_match = i < n and (p[j] == s[i] or p[j] == ".")

The i < n guard matters. A dot or literal consumes one character; it cannot match an empty suffix.

The next pattern character determines whether the current element is quantified:

has_star = j + 1 < m and p[j + 1] == "*"

The star is not handled as an ordinary character. It modifies p[j], so the recurrence must inspect the character after the current element.

Derive the ordinary and star recurrences

There are two cases.

Ordinary literal or dot

If p[j] is not followed by *, it must consume exactly one text character.

That requires:

1. s[i] exists and is compatible with p[j];
2. the remaining suffixes match.

Therefore:

match(i, j) = first_match and match(i + 1, j + 1)

A literal or dot advances both coordinates.

Element followed by *

Suppose p[j + 1] == '*'. The pair p[j:j+2] represents zero or more occurrences of p[j].

There are two branches.

Branch 1: zero occurrences

Skip both the element and its star:

match(i, j + 2)

The pattern advances by two. The text does not move.

For a*, this means: “Use zero a characters.”

Branch 2: one or more occurrences

To consume one occurrence:

1. s[i] must match p[j];
2. the same star must remain available for more occurrences.

So the transition is:

first_match and match(i + 1, j)

The text advances by one. The pattern index stays at j.

That unchanged j is the critical detail. Moving to j + 2 after one consumed character would allow only one occurrence, which is not the meaning of *.

Combining both branches:

match(i, j) =
    match(i, j + 2)
    or (first_match and match(i + 1, j))

The order of the branches does not affect correctness. I usually write the skip branch first because it makes the zero-occurrence interpretation explicit. Short-circuit evaluation may avoid exploring the second branch when the first already succeeds.

Recurrence table

Pattern situation	Required condition	Next state
Pattern exhausted	i == n	True
Pattern exhausted	i < n	False
Ordinary literal or .	first_match	match(i + 1, j + 1)
Ordinary literal or .	not first_match	False
Element followed by *, skip	none	match(i, j + 2)
Element followed by *, consume	first_match	match(i + 1, j)

The invariant is simple:

Every true transition consumes only text characters allowed by the current pattern element, and every transition preserves exactly the pattern suffix that remains available.

The skip branch and consume branch exhaust the legal interpretations of zero-or-more. There is no third star behavior to model.

Prove full-string correctness

The implementation is short. The proof is where the boundary conditions become trustworthy.

Terminal case

When j == m, the pattern suffix is empty.

• If i == n, both suffixes are empty, so the match is true.
• If i < n, text remains with no pattern available, so the match is false.

Thus the terminal condition enforces a complete match rather than a prefix match.

Ordinary token

Assume p[j] is not followed by *.

A valid match must assign exactly one text character to this pattern element. Therefore:

• If s[i] does not exist, the match fails.
• If s[i] is incompatible with p[j], the match fails.
• If the characters are compatible, the current pair is valid exactly when s[i+1:] matches p[j+1:].

That is precisely:

first_match and match(i + 1, j + 1)

The transition is both necessary and sufficient.

Star token

Assume p[j + 1] == '*'.

Any valid interpretation of p[j]* falls into one of two exhaustive categories:

1. It contributes zero occurrences. Then the match must continue with p[j+2:], producing match(i, j+2).
2. It contributes at least one occurrence. The first occurrence must match s[i], and after consuming it, the same p[j]* may consume more. That produces first_match and match(i+1,j).

This establishes completeness: every valid match appears in one of the branches.

For soundness, inspect the branches in reverse:

• The skip branch removes exactly the element-star unit, which is valid for zero occurrences.
• The consume branch consumes one character only when it matches the quantified literal or dot, then keeps the star available for further legal occurrences.

So every successful recursive path describes a legal match, and every legal match has a corresponding recursive path.

The final answer is:

match(0, 0)

Both suffixes must reach their ends together. The state does not merely ask whether the pattern can match some prefix of the text; it asks whether the two complete suffixes are equivalent under the restricted pattern rules.

Implement memoized DFS in Python

The recursive definition maps directly to a cached helper. Use indices rather than slicing. Creating s[i:] and p[j:] at every call would hide the state and repeatedly construct substrings.

from functools import cache


def is_match(s: str, p: str) -> bool:
    n = len(s)
    m = len(p)

    @cache
    def match(i: int, j: int) -> bool:
        # No pattern remains: success only if no text remains either.
        if j == m:
            return i == n

        first_match = (
            i < n
            and (p[j] == s[i] or p[j] == ".")
        )

        # p[j] is the element quantified by '*'.
        if j + 1 < m and p[j + 1] == "*":
            skip = match(i, j + 2)
            consume = first_match and match(i + 1, j)
            return skip or consume

        # Ordinary literal or dot: consume one character from each suffix.
        return first_match and match(i + 1, j + 1)

    return match(0, 0)

The control flow follows the proof:

1. Guard the exhausted-pattern boundary.
2. Compute whether the current text and pattern elements are compatible.
3. Inspect whether the next pattern character is *.
4. For a star, choose skip or consume.
5. Otherwise, consume one character from both sides.

This is the version I would write in an interview. The state is visible, the star branches are named, and the code does not bury the recurrence inside a table-index transformation.

functools.cache stores the Boolean result for each (i, j). A dictionary keyed by (i, j) is equivalent if the runtime or environment does not provide cache.

Trace empty suffixes and repeated tokens

Dry runs should focus on movement, not on narrating every Boolean.

Example: s = "aab", p = "c*a*b"

Start at (0, 0), where the current pattern unit is c*.

• c does not match a.
• The consume branch is unavailable.
• The skip branch moves to (0, 2), skipping c*.

Now the current unit is a*:

• At (0, 2), skip is possible: pretend a* contributes zero characters.
• The consume branch is also possible: a matches s[0], so move to (1, 2).
• At (1, 2), consume again and move to (2, 2).
• At (2, 2), s[2] is b, so a* cannot consume it. Skip to (2, 4).
• b matches s[2]; move to (3, 5).
• Both suffixes are exhausted, so return true.

The repeated-token path is:

(0, 2) -> (1, 2) -> (2, 2)

The pattern coordinate stays fixed while the text coordinate advances.

Empty text against a*b*c*

Consider:

s = ""
p = "a*b*c*"

The state begins at (0, 0):

(0, 0) -> (0, 2) -> (0, 4) -> (0, 6)

Each transition skips one element-star pair. At (0, 6), both suffixes are empty, so the result is true.

This is why i == n does not need a special pattern scan. The recurrence already knows that a star can disappear without consuming text.

A repeated-token failure: s = "aaa", p = "ab*a"

The pattern means:

a, then zero or more b characters, then a

At the beginning, the first a consumes s[0]. The state becomes (1, 1), where b* is next and the remaining text is "aa".

At b*:

• b cannot consume the current a.
• The skip branch moves past b* to the final a.
• That final a consumes one text character, but one a remains.

The match fails because the pattern has ended while text remains.

This example is useful because a failed consume branch must not cause the algorithm to forget the skip branch in general. Star branches are alternatives, not a one-time commitment.

Dot plus star: s = "ab", p = ".*"

At (0, 0), . matches a, so the consume branch keeps the state at the same pattern index:

(0, 0) -> (1, 0) -> (2, 0)

At (2, 0), the text is empty. The consume branch is unavailable, so skip .*:

(2, 0) -> (2, 2)

Both suffixes are now exhausted. The result is true.

The dot supplies one-character compatibility. The star supplies repetition, including zero repetitions.

The full-string trap: s = "aa", p = "a"

The first a matches:

(0, 0) -> (1, 1)

At (1, 1), the pattern is exhausted but one a remains. The base case returns false.

A matcher that returns true after consuming the pattern has implemented prefix matching, not this problem.

When debugging, use this loop:

1. Record the failing (i, j) state.
2. Identify whether the current unit is ordinary or starred.
3. For a star, inspect both skip and consume.
4. Check which coordinate should move.
5. Revisit the state definition before adding a patch.

Read the error. Trace the state. Fix the assumption.

Complexity and edge-case checklist

There are at most (n + 1)(m + 1) index pairs. Each cached state performs constant local work and makes at most two cached recursive calls.

Therefore:

• Time: O(nm)
• Memoization space: O(nm)
• Recursion stack: up to O(n + m) along a call path
• Total auxiliary space: O(nm + n + m), usually reported as O(nm) when the cache dominates

The supplied constraints are small, but the recurrence matters more than the input limit. This is the reusable part of the solution.

Before submitting, check:

• Empty pattern with nonempty text.
• Nonempty pattern with empty text.
• Both strings empty, if the implementation is tested beyond the stated input bounds.
• A pattern suffix made only of star pairs, such as a*b*c*.
• Zero repetitions: "b" against "a*b".
• One repetition: "ab" against "a*b".
• Many repetitions: "aaaa" against "a*".
• A literal mismatch.
• A dot matching exactly one character.
• .* matching an empty suffix and multiple characters.
• A trailing star pair.
• Multiple quantified tokens, such as a*b*c*.
• A prefix that matches while the full string does not, such as "aa" against "a".

The implementation checklist is compact:

1. Define match(i, j) as a suffix question.
2. Guard j == m before indexing p[j].
3. Compute first_match only when i < n.
4. Detect * by looking at p[j + 1].
5. Implement both star transitions.
6. Keep j fixed in the consume branch.
7. Advance j by two in the skip branch.
8. Require both suffixes to end together.
9. State cache and stack space separately.

The broader recognition rule is the part worth carrying into the next problem:

Use a two-index state when two forms of progress are independent, especially when one operation advances the second coordinate without consuming the first, while another consumes from the first and keeps the second coordinate available.

For this problem, * creates exactly that shape. Name the suffix state. Enumerate every legal transition. Prove the empty boundaries. Then test the branch that repeats one coordinate while the other moves.

That is how a pattern-matching problem stops looking like regex magic and becomes ordinary, auditable dynamic programming.