Regular Expression Matching

The character * never stands alone — it always modifies the character immediately before it in the pattern, so the pattern must always be consumed two tokens at a time whenever a * is next. That “look two ahead” quirk is what makes this DP’s recurrence a bit more intricate than a typical two-string comparison: a single decision (matching s[i] against p[j]) can require checking p[j+1] before knowing what to do.

Brute Force Recursion

Time O(2^(m+n))Space O(m+n)

At each pair of positions (i, j): first check whether the next pattern token is *. If so, that * can be used zero times (skip both p[j] and p[j+1], retry from p[j+2]) or, when the current characters are compatible, one-or-more times (consume s[i], retry from the same p[j] since * can repeat). If the next token isn’t *, it’s a plain one-character match.

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        def rec(i: int, j: int) -> bool:
            if j == len(p):
                return i == len(s)
            first_match = i < len(s) and p[j] in (s[i], '.')
            if j + 1 < len(p) and p[j + 1] == '*':
                zero_times = rec(i, j + 2)
                one_or_more = first_match and rec(i + 1, j)
                return zero_times or one_or_more
            return first_match and rec(i + 1, j + 1)
        return rec(0, 0)

Each * can branch into “use it” or “don’t”, and the same (i, j) state is reached through many different repeat counts — exponential blow-up.

2-D DP Table (Bottom-Up)

OptimalTime O(m·n)Space O(m·n)

dp[i][j] is true if s[0:i] matches p[0:j]. dp[0][0] is trivially true (empty matches empty). Row 0 (s empty) can still be true for patterns like a*b* — zero or more of everything — so it’s initialized by checking whether trailing x* pairs can all collapse to nothing. For the general cell: if p[j-1] is a plain character or ., it must match s[i-1] and the rest is dp[i-1][j-1]. If p[j-1] is *, either drop the x* pair entirely (dp[i][j-2]), or — if s[i-1] matches the character * is repeating — also allow dp[i-1][j] (use one more repetition, keeping the same pattern position).

class Solution:
    def isMatch(self, 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):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] in (s[i - 1], '.'):
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    dp[i][j] = dp[i][j - 2]
                    if p[j - 2] in (s[i - 1], '.'):
                        dp[i][j] = dp[i][j] or dp[i - 1][j]
                else:
                    dp[i][j] = False
        return dp[m][n]

Watch the table fill for statement example s = "aa", p = "a*" — the indigo cell is the one being decided, the amber cells are the already-computed inputs its rule reads (diagonal for a plain match, two cells back and straight up for a *), and emerald cells are the True answers that have accumulated:

s↓ p→

1 / 9

currentresultcomparingseen

Seed the corner: dp[0][0] = T — the empty string matches the empty pattern. Every other cell answers one pair of prefixes, and each builds on this corner.

The emerald chain down the a* column is the whole story: a* matches zero as (dp[0][2]), then one (dp[1][2]), then two (dp[2][2]) — every extend-branch read of the star rule, dp[i][j] = dp[i-1][j], consumes one more character of s while the pattern position never moves. The two-cells-back drop branch (dp[i][j-2]) is what zero repetitions means, and the seed row showed it firing in its purest form.

Two-star-group cases exercise the same rules in shapes that depend on the pattern, so it helps to read one aloud — working through s = "aab", p = "c*a*b" (two different * groups plus a trailing literal) in words:

p = "c*a*b" against empty s: c* can vanish (0 uses of c), and a* can vanish too, leaving just b — which doesn’t match empty s. So dp[0][j] is only true through the a* prefix, i.e. dp[0][2] (c* alone) and dp[0][4] (c*a*) are true, not dp[0][5].
Matching s[0]='a' against p: the c* group matches zero cs (since s has no leading c), then a* starts consuming as.
a* can consume both as in "aab" (one or more repetitions extend dp[i-1][j] forward each time s[i-1] == 'a'), landing on dp[2][4] = True — two as consumed, c*a* fully matched.
Finally b matches the trailing b in s, giving dp[3][5] = True — confirmed by running the code above: isMatch("aab", "c*a*b") returns True.

Complexity: each of the (m+1)·(n+1) cells does O(1) additional work (checking two pattern characters) → O(m·n) time, O(m·n) space.

Top-Down Memoization

Time O(m·n)Space O(m·n)

The recursive formulation from the brute-force solution is arguably easier to read than the bottom-up table here, because the “look at p[j+1]” logic reads naturally as “peek ahead” rather than as index arithmetic on j-2. Adding a memo cache turns it from exponential into polynomial without changing its structure at all.

from functools import cache

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @cache
        def rec(i: int, j: int) -> bool:
            if j == len(p):
                return i == len(s)
            first_match = i < len(s) and p[j] in (s[i], '.')
            if j + 1 < len(p) and p[j + 1] == '*':
                return rec(i, j + 2) or (first_match and rec(i + 1, j))
            return first_match and rec(i + 1, j + 1)
        return rec(0, 0)

Complexity: at most (m+1)·(n+1) distinct (i, j) states are ever computed, each doing O(1) work — O(m·n) time, O(m·n) space for the cache plus recursion stack.