Skip to main content

82. Regular Expression Matching

hardAsked at Snowflake

Implement regex matching with . and *. Snowflake asks this for 2D DP with branching transitions — directly relevant to their REGEXP_LIKE evaluator and LIKE pattern matching.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake function-team uses this for REGEXP_LIKE implementation discussion.
  • LeetCode Discuss (2025-10)— Reported at Snowflake SDE-II onsites.

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 <= 30
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '.', and '*'.

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 without memoization

match(i, j): handle '*' by either skipping or consuming (if current char matches).

Time
O(2^(m+n))
Space
O(m+n)
// outline only — exponential.

Tradeoff: Exponential. Mention to reject.

2. 2D DP (optimal)

dp[i][j] = whether s[:i] matches p[:j]. Transitions on regular char, '.', and '*' (zero copies or consume one).

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 = 2; 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] === '*') {
        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]; // one more copy
        }
      } else if (p[j - 1] === '.' || p[j - 1] === s[i - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      }
    }
  }
  return dp[m][n];
}

Tradeoff: O(mn) time and space. The '*' branch tries both 'zero copies' and 'one more copy'.

Snowflake-specific tips

Snowflake interviewers want the two '*' transitions explained: zero copies (dp[i][j-2]) and consume one (dp[i-1][j] if last char matches). Bonus signal: discuss how REGEXP_LIKE differs (Snowflake uses an NFA/DFA hybrid for performance) and what trade-offs that makes.

Common mistakes

  • Treating '*' as 'one or more' — it's zero or more.
  • Forgetting the dp[0][j] initialization for patterns like 'a*b*c*' that match empty string.
  • Off-by-one between dp index i and string index i-1.

Follow-up questions

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

  • Wildcard Matching (LC 44) — different semantics for '*'.
  • How does Snowflake's REGEXP_LIKE implementation work?
  • Convert to NFA/DFA.

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[i][j-2] for the zero-copies '*' branch?

* with zero copies means we skip the entire 'char*' (2 characters) in the pattern, leaving s[:i] to match p[:j-2].

Why dp[i-1][j] for the consume branch?

If s[i-1] matches the char before *, we 'consume' one s char without advancing the pattern — leaving s[:i-1] to match p[:j].

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →