← All problems

String dynamic programming · recursion + memoization

Regular Expression Matching

Input: a string s and a pattern p. Output: True if the pattern matches the entire string; otherwise False. A letter matches itself, . matches any one character, and * means zero or more copies of the element immediately before it. The pattern is valid: * never appears first or directly after another *. This is full matching, not searching for a substring.

One extra letters = "aa"p = "a"

False. The pattern leaves one a unmatched.

Repeat a letters = "aa"p = "a*"

True. a* can consume both letters.

Skip and matchs = "aab"p = "c*a*b"

True. Use zero cs, two as, then b.

01 / Build the recursion without *

What does solve(i, j) mean?

solve(i, j) asks whether the remaining string s[i:] matches the remaining pattern p[j:]. The answer we want is solve(0, 0). First imagine that the pattern contains only letters and ..

Both exhausted → True

i == len(s) and j == len(p): every character matched.

Pattern exhausted → False

j == len(p) while i < len(s): characters remain in the string.

String exhausted → False

i == len(s) while j < len(p): without *, every remaining pattern element needs a character.

If both current characters exist, they match when s[i] == p[j] or p[j] == '.'. Only then do both indices advance.

without *: solve(i, j) = first_match and solve(i + 1, j + 1)

This first version deliberately assumes the pattern has no *:

def match_without_star(s: str, p: str) -> bool:
    def solve(i: int, j: int) -> bool:
        if j == len(p):
            return i == len(s)  # Both ended, or s still has characters.
        if i == len(s):
            return False        # Remaining pattern needs a character.

        first_match = p[j] == s[i] or p[j] == "."
        return first_match and solve(i + 1, j + 1)

    return solve(0, 0)

02 / Add * carefully

Look ahead before advancing

The third base case is no longer valid.

An empty string matches "a*": choose zero as. So, when i == len(s), keep evaluating the pattern. Only an exhausted pattern gives a final base answer.

At state (i, j), check whether p[j + 1] == '*'. If it is, the element p[j]* creates two choices. We must decide here; blindly calling solve(i + 1, j + 1) would land on * and lose its meaning.

Zero copies · skip the pair

solve(i, j + 2) keeps the string index and moves past the element and its *. This works even when the string is already empty.

One or more · consume one

If i < len(s) and the element matches s[i], call solve(i + 1, j). Keep j so the same pair can consume another character.

with next *: solve(i, j) = solve(i, j + 2) or (first_match and solve(i + 1, j))

Without a following *, require first_match and advance both indices. A failed first match simply returns False.

03 / Interactive call trace

Watch the recursive choices

Each table cell is a state (i, j). Saved answers are reused when a state appears again.

Memoized suffix states
Current stateSkip zero copiesConsume one copySaved result

String s · indices

Pattern p · indices

Memo table · row i, column j

Active recursive calls

04 / Python solution

Memoize each pair of indices

The code checks the pattern boundary first. Its first_match expression is safe when the string is empty, and @cache computes each reachable (i, j) at most once.

from functools import cache

def is_match(s: str, p: str) -> bool:
    @cache
    def solve(i: int, j: int) -> bool:
        if j == len(p):
            return i == len(s)

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

        if j + 1 < len(p) and p[j + 1] == "*":
            # Zero copies, or consume one and try the same pattern again.
            return solve(i, j + 2) or (first_match and solve(i + 1, j))

        return first_match and solve(i + 1, j + 1)

    return solve(0, 0)

print(is_match("aab", "c*a*b"))  # True

There are at most (len(s) + 1) × (len(p) + 1) states. Memoization gives O(len(s) × len(p)) time and space, including the recursion stack within that bound.

Regular Expression Matching · Algorithm Atlas