Regular Expression Matching — InterviewPrepKit

Solving tips

Set up prefix-vs-prefix DP: dp[i][j] = does s[:i] match p[:j], and require the WHOLE string to match (answer is dp[m][n]).
The '*' case is the crux: dp[i][j] = dp[i][j-2] (zero copies of the preceding element) OR (preceding element matches s[i-1] AND dp[i-1][j]) (one more copy) — the repeated char is p[j-2], not p[j-1].
'*' means zero-or-more of the SINGLE preceding element, not 'any sequence'; a* matches only a's.
Seed the empty-string first row so patterns like a*b* match '' via dp[0][j]=dp[0][j-2]. Target O(m*n) time, O(n) space.

Problem

Given an input string s and a pattern p, decide whether p matches the entire string s. The pattern supports two special characters:

. matches any single character.
* matches zero or more of the character immediately preceding it.

A * always follows a valid character or .; it never appears first. The match must cover all of s, not just a prefix.

Examples

s = "aa", p = "a" → False — "a" matches only one character, not the whole "aa".
s = "aa", p = "a*" → True — a* expands to two a’s.
s = "ab", p = ".*" → True — .* is “zero or more of any character”, covering "ab".

Constraints

1 <= len(s) <= 20, 1 <= len(p) <= 30 (roughly)
s is lowercase letters; p is lowercase letters plus . and *.
Every * has a valid preceding element.
Small bounds, but the branching from * (match zero vs. match one-more) makes an O(len(s)·len(p)) table the clean solution.

Think about it first

Hint 1

Match prefixes: ask whether the first `i` characters of `s` match the first `j` characters of `p`. The hard case is when `p[j-1]` is a `*`, because `*` (with its preceding char) can consume zero, one, or many characters of `s`.

Hint 2

When `p[j-1]` is not `*`: the last characters must line up — `s[i-1]` equals `p[j-1]` or `p[j-1]` is `.`, and the shorter prefixes must already match. When `p[j-1]` is `*`: either use it as **zero** copies (drop the `char*` pair, i.e. look at `p[:j-2]`), or, if `p[j-2]` matches `s[i-1]`, use **one more** copy (keep the pattern, drop one char of `s`).

Hint 3

`dp[i][j]` = does `s[:i]` match `p[:j]`. For `p[j-1] == '*'`: `dp[i][j] = dp[i][j-2] or (matches(s[i-1], p[j-2]) and dp[i-1][j])`. Otherwise `dp[i][j] = matches(s[i-1], p[j-1]) and dp[i-1][j-1]`. Seed `dp[0][0] = True` and handle empty-string-vs-`a*b*` patterns in the first row.

TL;DR

Prefix-matching DP: dp[i][j] = does s[:i] match p[:j], with a special * transition that means “zero copies or one-more copy” — O(len(s)·len(p)) time, O(len(p)) space with two rolling rows.

Approach 1 — Brute force recursion

Match from the front. A * at p[j+1] branches into “use zero copies” (skip p[j]p[j+1]) or “consume one character of s and stay on the same pattern”.

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

Complexity: exponential — a * repeatedly forks into zero/one-more, and the same (i, j) pair is revisited along many branches.

Approach 2 — Top-down memoization

The insight: whether s[i:] matches p[j:] depends only on (i, j). There are (len(s)+1)·(len(p)+1) such pairs, so caching turns the exponential recursion into a linear-in-area computation.

State / recurrence. match(i, j) = does the suffix s[i:] match the suffix p[j:]. Let first = s[i] is present and equals p[j] (or p[j] == '.'). If p[j+1] == '*': match(i, j) = match(i, j+2) or (first and match(i+1, j)). Otherwise match(i, j) = first and match(i+1, j+1). Base: match(len(s), len(p)) = True.

from functools import lru_cache

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @lru_cache(maxsize=None)
        def match(i: int, j: int) -> bool:
            if j == len(p):
                return i == len(s)
            first = i < len(s) and (p[j] == '.' or p[j] == s[i])
            if j + 1 < len(p) and p[j + 1] == '*':
                return match(i, j + 2) or (first and match(i + 1, j))
            return first and match(i + 1, j + 1)
        return match(0, 0)

Complexity: O(len(s)·len(p)) time and space.

Approach 3 — Bottom-up tabulation (the 2-D table)

State / recurrence. dp[i][j] = does the prefix s[:i] match the prefix p[:j]. Write hit(i, j) for “p[j-1] matches s[i-1]”, i.e. p[j-1] == '.' or p[j-1] == s[i-1].

dp[0][0] = True
dp[0][j] = dp[0][j-2]                          if p[j-1] == '*'   (char* matches empty)
For i >= 1:
  if p[j-1] == '*':
      dp[i][j] = dp[i][j-2]                     # zero copies of p[j-2]
                 or (hit(i, j-1) and dp[i-1][j]) # one more copy, if p[j-2] matches s[i-1]
  else:
      dp[i][j] = hit(i, j) and dp[i-1][j-1]

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] == '*':
                    dp[i][j] = dp[i][j - 2]
                    if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                        dp[i][j] = dp[i][j] or dp[i - 1][j]
                else:
                    if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                        dp[i][j] = dp[i - 1][j - 1]
        return dp[m][n]

Walkthrough with s = "aa", p = "a*" (m=2, n=2). First row: dp[0][0] = True; p[1] == '*' so dp[0][2] = dp[0][0] = True (a* matches empty). Row i=1: at j=2 (*), dp[1][2] = dp[1][0] (False) or (p[0]=='a'==s[0] and dp[0][2]=True) → True. Row i=2: at j=2, dp[2][2] = dp[2][0] (False) or ('a'==s[1] and dp[1][2]=True) → True. So dp[2][2] = True.

Complexity: O(m·n) time, O(m·n) space.

Approach 4 — Space-optimized (two rolling rows)

The insight: the * case reads dp[i-1][j] (row above) and dp[i][j-2] (same row, earlier). Only the previous row is needed, so keep prev and build curr.

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        prev = [False] * (n + 1)
        prev[0] = True
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                prev[j] = prev[j - 2]
        for i in range(1, m + 1):
            curr = [False] * (n + 1)
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    curr[j] = curr[j - 2]
                    if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                        curr[j] = curr[j] or prev[j]
                else:
                    if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                        curr[j] = prev[j - 1]
            prev = curr
        return prev[n]

Complexity: O(m·n) time, O(n) space.

Common pitfalls

Treating * as “any sequence” (that is glob/.*), instead of “zero or more of the single preceding element”. a* is only a’s.
Forgetting the empty-string first row: a pattern like "a*b*" must match "", which needs dp[0][j] = dp[0][j-2] seeding.
In the * branch, checking the wrong preceding character — the repeated element is p[j-2], not p[j-1].
Matching a prefix rather than the whole string; the answer is dp[m][n], requiring both to be fully consumed.

Pattern takeaway

Prefix-vs-prefix matching between two sequences is a 2-D DP indexed by how much of each you have consumed. Operators that consume a variable amount (like *) become an OR over their possible expansions — here “zero copies” (dp[i][j-2]) OR “one more copy” (dp[i-1][j]). Isolate a small matches(char, patternChar) predicate, enumerate the pattern’s cases, and the table writes itself; then collapse to rolling rows since only the previous row is read.