Mini Regex Matcher (. and *)

Start from brute force

The obvious approach is to recurse on the two choices directly. match(i, j) returns i == len(s) once the pattern is used up; at a starred element it tries match(i, j + 2) (zero copies) and, if the character matches, match(i + 1, j) (one more copy); otherwise it needs first and match(i + 1, j + 1). It is correct, because it tries every way a star can split the string. But it solves the same (i, j) pairs again and again, so time is exponential in the worst case: on s = 'a' * 16 and p = 'a*' * 8 + 'b' it makes 1,817,045 calls where the table has 306 cells. Space is O(len(s) + len(p)) for the recursion stack.

The approach

The insight is that every state of the match is a pair of positions: how much of s is left and how much of p is left. There are only (ls + 1)(lp + 1) such pairs, so solve each once. dp[i][j] answers “does s[i:] match p[j:]?”, and every cell depends only on cells below it or to its right, so the reference fills the table from the end, starting from dp[ls][lp] = True (empty matches empty).

The outer loop starts at i = ls, not ls - 1, because the empty-suffix row is where starred elements match nothing. For each cell, first says whether p[j] matches s[i] (a literal or ., and only while i < ls). If p[j + 1] is *, the cell is dp[i][j + 2] (zero copies: skip the pair) or first and dp[i + 1][j] (one copy, staying on the same element so it can take more). Otherwise it is first and dp[i + 1][j + 1]. The answer is dp[0][0].

Walk through an example

The second example, s = 'aa' and p = 'a*', filled in the reference's order (i from 2 down to 0, j from 1 down to 0), because the first example never reaches the star branch.

Complexity

DP: O(ls · lp) time, because each of the (ls + 1)(lp + 1) cells is filled once with constant work, and O(ls · lp) space for the table; keeping only rows i and i + 1 cuts space to O(lp). Brute-force recursion: exponential time in the worst case, because it re-solves the same (i, j) pairs, and O(ls + lp) stack space.

Edge cases to test

• s = '', p = '': True, from the base cell alone.
• s = '', p = 'a*b*.*': True. Every pair takes zero copies, which only works because the loop fills the row i = ls.
• s = 'aaa', p = 'a*a': True. The star has to leave one a for the final literal; a greedy matcher that lets a* take all three returns False.
• s = 'ab', p = '.*c': False. .* can take any prefix, but nothing supplies the c.
• s = 'mississippi', p = 'mis*is*p*.': False. After mi, ss, i, ss, only p* and one . remain for ippi.
• s = 'a', p = 'ab*': True. A trailing starred element matches nothing.

Common mistakes

• Handling * greedily, letting a* take every a and never give one back: is_match('aaa', 'a*a') and is_match('ab', '.*b') both come out False instead of True.
• Letting . match past the end of the string.
• No memoization, so overlapping subproblems explode exponentially.
• Starting the outer loop at ls - 1. The empty-suffix row stays False, so a* can never match nothing and is_match('aa', 'a*') returns False.
• Writing dp[i + 1][j] and first instead of first and dp[i + 1][j]. At i = ls the short-circuit is what stops the read of row ls + 1, which does not exist: is_match('', 'a*b') then raises IndexError in Python and TypeError in TypeScript.

Follow-ups an interviewer asks next

Add + (one or more) and ? (zero or one).

Both fit the same table. For x+ at j, the cell is first and (dp[i + 1][j] or dp[i + 1][j + 2]): consume one copy, then stay for more or move past the pair. For x? it is dp[i][j + 2] or (first and dp[i + 1][j + 2]): skip it, or consume exactly one and move on. The recurrence changes; the O(ls · lp) bound does not.

Wildcard matching instead: ? is one character and * is any sequence.

Now the star stands alone instead of repeating the element before it. For a star at j, dp[i][j] = dp[i][j + 1] or (i < ls and dp[i + 1][j]): match nothing, or swallow one character and stay on the star. ? behaves like the dot here. Same two-index table, same O(ls · lp) time and space.

Can you do it in O(lp) memory?

Yes. Row i reads only itself and row i + 1, so keep two arrays of length lp + 1 and swap them after each i. Fill each row from j = lp − 1 down to 0, because a star cell reads dp[i][j + 2] from the same row, and set the last cell to True only in the first row filled (i = ls), the base case.

How do production regex engines avoid exponential time?

Engines such as RE2 and Rust's regex crate compile the pattern to an automaton and track every live state at once (Thompson's construction), which runs in time linear in the input for a fixed pattern. Backtracking engines, including Python's re, can take exponential time on patterns like (a*)*b, which is the ReDoS risk. The price of the automaton approach is giving up backreferences.

Where this shows up

This tiny matcher is the conceptual core of regular expressions. Real engines compile to an NFA/DFA for speed, but the “* means try both branches” recursion is the same idea — and it explains catastrophic backtracking, the pathological slowdown behind real-world ReDoS bugs.

Reference solution

def is_match(s, p):
    ls, lp = len(s), len(p)
    # dp[i][j] = does s[i:] match p[j:] ?
    dp = [[False] * (lp + 1) for _ in range(ls + 1)]
    dp[ls][lp] = True                       # empty vs empty
    for i in range(ls, -1, -1):
        for j in range(lp - 1, -1, -1):
            first = i < ls and (p[j] == s[i] or p[j] == ".")
            if j + 1 < lp and p[j + 1] == "*":
                dp[i][j] = dp[i][j + 2] or (first and dp[i + 1][j])  # zero, or one+stay
            else:
                dp[i][j] = first and dp[i + 1][j + 1]                # consume one
    return dp[0][0]


print(is_match("aa", "a"))            # -> False
print(is_match("aa", "a*"))           # -> True
print(is_match("aab", "c*a*b"))       # -> True

function isMatch(s: string, p: string): boolean {
  const ls = s.length, lp = p.length;
  // dp[i][j] = does s[i:] match p[j:] ?
  const dp: boolean[][] = Array.from({ length: ls + 1 }, () => new Array(lp + 1).fill(false));
  dp[ls][lp] = true;
  for (let i = ls; i >= 0; i--) {
    for (let j = lp - 1; j >= 0; j--) {
      const first = i < ls && (p[j] === s[i] || p[j] === ".");
      if (j + 1 < lp && p[j + 1] === "*") {
        dp[i][j] = dp[i][j + 2] || (first && dp[i + 1][j]);   // zero, or one+stay
      } else {
        dp[i][j] = first && dp[i + 1][j + 1];                 // consume one
      }
    }
  }
  return dp[0][0];
}

console.log(isMatch("aa", "a"));        // -> false
console.log(isMatch("aa", "a*"));       // -> true
console.log(isMatch("aab", "c*a*b"));   // -> true