Skip to main content

90. Regular Expression Matching

hardAsked at Reddit

Implement regex matching for '.' and '*'. Reddit uses this DP problem to test state-machine thinking — the same shape used when implementing custom rule-based content filters in their AutoModerator engine.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit content-platform hard question.

Problem

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' 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, '.', and '*'.
  • 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. Recursive backtracking

If p[j+1] === '*', try zero matches (skip p[j..j+1]) or one+ matches (consume s[i] if matches).

Time
exponential
Space
O(s + p)
function isMatch(s, p) {
  function match(i, j) {
    if (j === p.length) return i === s.length;
    const first = i < s.length && (p[j] === '.' || p[j] === s[i]);
    if (j + 1 < p.length && p[j + 1] === '*') {
      return match(i, j + 2) || (first && match(i + 1, j));
    }
    return first && match(i + 1, j + 1);
  }
  return match(0, 0);
}

Tradeoff: Exponential without memo.

2. DP with memoization (optimal)

Same recursion + memo[i][j].

Time
O(s * p)
Space
O(s * p)
function isMatch(s, p) {
  const memo = new Map();
  function match(i, j) {
    const key = `${i},${j}`;
    if (memo.has(key)) return memo.get(key);
    let result;
    if (j === p.length) result = i === s.length;
    else {
      const first = i < s.length && (p[j] === '.' || p[j] === s[i]);
      if (j + 1 < p.length && p[j + 1] === '*') {
        result = match(i, j + 2) || (first && match(i + 1, j));
      } else {
        result = first && match(i + 1, j + 1);
      }
    }
    memo.set(key, result);
    return result;
  }
  return match(0, 0);
}

Tradeoff: Linear in state space. Bottom-up DP would also work.

Reddit-specific tips

Reddit interviewers grade on the 'zero matches' vs. 'one+ matches' branching for *. Bonus signal: walk through 'aa' vs. 'a*' showing both branches at j=0 (try j+=2 = skip; try i+=1 = consume).

Common mistakes

  • Treating * as matching any sequence (it modifies the preceding char).
  • Forgetting the i < s.length guard before comparing s[i].
  • Off-by-one when peeking at p[j+1] without checking bounds.

Follow-up questions

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

  • Wildcard matching (LC 44) — '?' and '*'.
  • Edit distance (LC 72).
  • Bottom-up DP version.

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 two branches for *?

* can match zero (skip the c* pair) or one+ chars (consume s[i] if c matches s[i], stay at j).

What if s and p are both empty?

Match (both pointers at end). The base case j === p.length and i === s.length returns true.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →