96. Regular Expression Matching

hardAsked at Vercel

Implement regex matching with '.' (any char) and '*' (zero or more). Vercel asks this for the 2D DP that handles backtracking cleanly — same shape as their route-pattern matcher with wildcards.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Vercel loops.

Glassdoor (2025-Q4)— Vercel routing-team onsite; DP-based regex match expected.
Blind (2026-Q1)— Listed as a Vercel hard.

Problem

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

Constraints

1 <= s.length <= 20
1 <= p.length <= 20
s contains only lowercase English letters.
p contains only lowercase English letters, '.', or '*'.
It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

Examples

Example 1

Input

s = "aa", p = "a"

Output

false

Example 2

Input

s = "aa", p = "a*"

Output

true

Example 3

Input

s = "ab", p = ".*"

Output

true

Approaches

1. Plain recursion

Match char-by-char; on '*', try zero-or-more.

Time: exponential
Space: O(n)

// Exponential blow-up on patterns like 'a*a*a*' against long inputs.

Tradeoff: Memoize.

2. 2D DP (optimal)

dp[i][j] = does s[0..i) match p[0..j)? Three cases: p[j-1] is a char (dp[i-1][j-1] AND chars match); '.' (dp[i-1][j-1]); '*' (dp[i][j-2] for zero copies, or dp[i-1][j] if preceding char matches).

Time: O(m*n)
Space: O(m*n)

function isMatch(s, p) {
  const m = s.length, n = p.length;
  const dp = Array.from({length: m + 1}, () => new Array(n + 1).fill(false));
  dp[0][0] = true;
  for (let j = 1; j <= n; j++) {
    if (p[j - 1] === '*') dp[0][j] = dp[0][j - 2];
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === '.' || p[j - 1] === s[i - 1]) dp[i][j] = dp[i - 1][j - 1];
      else if (p[j - 1] === '*') {
        dp[i][j] = dp[i][j - 2]; // zero copies
        if (p[j - 2] === '.' || p[j - 2] === s[i - 1]) {
          dp[i][j] = dp[i][j] || dp[i - 1][j];
        }
      }
    }
  }
  return dp[m][n];
}

Tradeoff: O(mn) time and space. The three cases require careful articulation of what each transition represents.

Vercel-specific tips

Vercel grades the DP recurrence and the three cases. Bonus signal: the empty-string vs pattern-with-stars initialization (dp[0][j] for patterns like 'a*b*' should be true at the * positions). Most candidates miss this row initialization.

Common mistakes

Forgetting the empty-string-pattern row init (dp[0][j] for j >= 2 with star).
Confusing 'star matches preceding char' with 'star matches any char' — only the preceding char.
Off-by-one: dp[i][j] = match for s[0..i) and p[0..j), so accesses use [i-1] and [j-1].

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

Wildcard Matching (LC 44) — '?' and '*' (different semantics).
Convert to NFA/DFA for repeated matching against many strings.
Memoized recursion as an alternative.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why dp[0][j] initialization?

Patterns like 'a*' or 'a*b*' can match the empty string. The init handles this: dp[0][j] = true iff p[j-1] is '*' and dp[0][j-2] is true (the '*' contributes zero copies).

Why dp[i-1][j] for the 'star matches one more' case?

If 'a*' has already consumed some 'a's (dp[i-1][j] is true), we can extend by matching one more 'a' at position i — keeping the same dp[j] (the star pattern remains active).

Practice these live with InterviewChamp.AI

Drill Regular Expression Matching and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →