10. Regular Expression Matching

Q: Why memoization over plain recursion?

The recursive version hits the same (i, j) state through different paths — patterns like 'a*a*a*' explode exponentially without caching. Memo collapses identical subproblems to a single O(1) lookup.

Q: Top-down or bottom-up — which does Uber prefer?

Both score equally on correctness and complexity. Top-down with memo is usually faster to write correctly under interview pressure; bottom-up has cleaner memory layout. Pick what you can write bug-free.

hardAsked at Uber

Implement regex matching with '.' (any single char) and '*' (zero or more of the previous). Uber asks this to test 2-D DP fluency: are you comfortable writing the recurrence, then memoizing it bottom-up?

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

Source citations

Public interview reports confirming this problem appears in Uber loops.

Glassdoor (2026-Q1)— Uber senior+ onsite reports include this as a recurring DP hard.
Blind (2025-11)— Mentioned in Uber 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

Explanation: 'a*' means zero or more 'a's; matches 'aa'.

Example 3

Input

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

Output

true

Explanation: '.*' means zero or more of any char.

Approaches

1. Recursive (no memo)

If next pattern char is '*', either skip 'x*' in pattern or consume one char if it matches. 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 to reason about but blows up on patterns like 'a*a*a*a*b'. Memoize or DP-it for production-grade.

2. Top-down DP with memoization

Cache (i, j) where i and j index into s and p. Same recurrence as above but each state computed once.

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

function isMatchMemo(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 in time and space. Often the easiest to write under interview pressure because the recurrence is the same as the recursive version.

3. Bottom-up DP (table)

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

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[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: No recursion overhead, deterministic memory access pattern. Slightly trickier to write under pressure but slightly faster constants.

Uber-specific tips

Uber interviewers want the recurrence stated out loud before any code: 'If the next pattern char is *, I have two choices — skip the x* entirely, or consume one char if it matches. Otherwise consume one on both sides.' Then they want to see you memoize. Diving into the bottom-up table without articulating the recurrence loses signal even if the code works.

Common mistakes

Confusing regex '.' with shell glob '?' — they have the same meaning here but '*' differs from glob.
Forgetting that '*' modifies the PREVIOUS char, not the next. 'a*' matches zero or more 'a'.
Off-by-one on the table dimensions (need m+1 and n+1 for empty-string base case).

Follow-up questions

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

Wildcard matching (LC 44) — '?' = any single, '*' = any sequence including empty. Different DP.
What if you added '+' (one or more)?
What if patterns could be compiled and reused across many strings? (Build an NFA/DFA once.)

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

The recursive version hits the same (i, j) state through different paths — patterns like 'a*a*a*' explode exponentially without caching. Memo collapses identical subproblems to a single O(1) lookup.

Top-down or bottom-up — which does Uber prefer?

Both score equally on correctness and complexity. Top-down with memo is usually faster to write correctly under interview pressure; bottom-up has cleaner memory layout. Pick what you can write bug-free.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →