Skip to main content

10. Regular Expression Matching

hardAsked at Airbnb

Implement regex matching with '.' (any single char) and '*' (zero or more). Airbnb asks this to test whether you can write the 2D DP recurrence and articulate why memoization beats raw recursion.

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

Source citations

Public interview reports confirming this problem appears in Airbnb loops.

  • Glassdoor (2026-Q1)— Airbnb senior+ onsite reports include this as a recurring DP hard.
  • Blind (2025-11)— Mentioned in Airbnb L5 algorithm-track interviews.

Problem

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where '.' matches any single character and '*' 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 '*' 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 (no memo)

If next pattern char is '*', either skip 'x*' or consume one matching char. Otherwise consume one char on both sides.

Time
Exponential worst case
Space
O(s + p) recursion
function isMatchRec(s, p) {
  if (p.length === 0) return s.length === 0;
  const first = s.length > 0 && (p[0] === s[0] || p[0] === '.');
  if (p.length >= 2 && p[1] === '*') {
    return isMatchRec(s, p.slice(2)) || (first && isMatchRec(s.slice(1), p));
  }
  return first && isMatchRec(s.slice(1), p.slice(1));
}

Tradeoff: Clean recurrence. Blows up on patterns like 'a*a*a*a*b'. Memoize.

2. Top-down DP with memo (optimal-readable)

Memoize on (i, j). Same recurrence; each state computed once.

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

Tradeoff: Polynomial. Often easiest to write correctly under interview pressure because it mirrors the recursion.

3. Bottom-up DP table

dp[i][j] = whether s[i:] matches p[j:]. Fill from bottom-right outward.

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

Tradeoff: Same complexity; no recursion overhead. Slightly trickier to write correctly under pressure.

Airbnb-specific tips

Airbnb wants the recurrence stated before any code. Say: 'For pattern[j], if pattern[j+1] is *, I have two choices — skip x* entirely, or consume one char if it matches. Otherwise consume one on both sides.' Then memo or table — both pass. Skipping the recurrence and writing the table is a flag.

Common mistakes

  • '*' modifies the PREVIOUS char, not the next.
  • Confusing this with wildcard matching (LC 44) — '*' there means any sequence, not 'zero or more of preceding'.
  • Off-by-one on dp table dimensions (need m+1 and n+1 for empty-string base).

Follow-up questions

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

  • Wildcard matching (LC 44) — '?' = single, '*' = sequence. Different DP recurrence.
  • What if you added '+' (one or more)?
  • Compile-once-match-many — build an NFA/DFA from the pattern.

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 memo over plain recursion?

Patterns like 'a*a*a*' hit the same (i, j) through different paths and explode exponentially. Memo caches each state to O(1).

Top-down memo or bottom-up table — which is better?

Both score equally on correctness and complexity. Memo is usually faster to write correctly under interview pressure; table has cleaner memory access patterns.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →