Skip to main content

10. Regular Expression Matching

hardAsked at Google

Implement regex matching with '.' and '*'. Google asks this to test whether you can set up a 2D DP for a problem where the recurrence has multiple branches depending on what character pattern[j-1] is.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L5+ onsite reports cite this as the algorithmic-thinking round.
  • Blind (2025-09)— Less common but recurring Google senior IC 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

Explanation: "a" does not match the entire string "aa".

Example 2

Input
s = "aa", p = "a*"
Output
true

Explanation: '*' means zero or more of the preceding element, 'a'.

Example 3

Input
s = "ab", p = ".*"
Output
true

Explanation: ".*" means "zero or more (*) of any character (.)".

Approaches

1. Recursion (exponential)

Recurse: if next pattern char is '*', try zero or more matches of the preceding element. Else match char-by-char.

Time
O(2^(m+n))
Space
O(m+n)
function isMatchRec(s, p) {
  if (p.length === 0) return s.length === 0;
  const firstMatch = s.length > 0 && (p[0] === '.' || p[0] === s[0]);
  if (p.length >= 2 && p[1] === '*') {
    return isMatchRec(s, p.slice(2)) || (firstMatch && isMatchRec(s.slice(1), p));
  }
  return firstMatch && isMatchRec(s.slice(1), p.slice(1));
}

Tradeoff: Captures the recurrence clearly. Adding memoization gets you to the DP. Mention this before writing the bottom-up version.

2. Bottom-up 2D DP (optimal)

dp[i][j] = can s[0..i] match p[0..j]. If p[j-1] is '*': try matching zero (dp[i][j-2]) or one+ (dp[i-1][j] AND chars match).

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

Tradeoff: Bottom-up DP — same complexity as memoized recursion but no recursion stack. The key insight: when seeing '*', try ZERO of the preceding (skip the pair) or ONE+ (consume from s, stay at same j).

Google-specific tips

Google interviewers grade this on whether you handle the '*' recurrence cleanly. State the two cases out loud: 'When I see *, I have two options — match zero copies (dp[i][j-2]) or match one+ copies (dp[i-1][j] if preceding matches).' Also handle the base case: dp[0][j] when the pattern is something like 'a*b*c*' that matches empty.

Common mistakes

  • Forgetting that '*' matches ZERO or more, not one or more.
  • Mishandling the base case for patterns like 'a*b*' against an empty string.
  • Confusing which index in the DP corresponds to the matched chars (off-by-one with i-1, j-1).

Follow-up questions

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

  • Add '+' (one or more) and '?' (zero or one).
  • Wildcard matching with '?' and '*' (LC 44 — different rules).
  • What if the pattern is a full regex (parens, |, anchors)?

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 2D DP and not 1D?

The recurrence references dp[i-1][j], dp[i][j-2], dp[i-1][j-1] — all different rows or columns. You can compress to two rows of width n+1, but not to a single row.

Is NFA/Thompson construction expected?

Not for a 45-minute interview. The DP solution is what Google interviewers expect; NFA is overkill and you won't finish.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →