91. Regular Expression Matching

Q: Why the dp[0][j] init loop?

Patterns like 'a*b*c*' can match the empty string. The init loop handles those cases.

Q: How does the '*' transition work?

Two cases: skip the *-group entirely (dp[i][j-2]) or consume one matched char (dp[i-1][j], if the char matches).

hardAsked at Datadog

Implement regex matching with '.' and '*'. Datadog asks this as a hard DP — same shape as their tag-pattern engine that matches user-specified wildcards against high-cardinality metric names.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

Glassdoor (2026-Q1)— Datadog onsite — direct tag-pattern matching analog.

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, '.', 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 without memo

Branch on whether pattern[1] is '*'.

Time: exponential
Space: O(n + m)

// Recurse with branches: if next is '*', try (skip the *-group) or (consume one if match).

Tradeoff: Exponential. Datadog requires DP or memo.

2. 2D DP (optimal)

dp[i][j] = does s[0..i-1] match p[0..j-1]. Handle '*' as: 'use zero of preceding' (dp[i][j-2]) or 'consume one' (if match, dp[i-1][j]).

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

function isMatch(s, p) {
  const n = s.length, m = p.length;
  const dp = Array.from({length: n + 1}, () => new Array(m + 1).fill(false));
  dp[0][0] = true;
  for (let j = 1; j <= m; j++) {
    if (p[j - 1] === '*') dp[0][j] = dp[0][j - 2];
  }
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (p[j - 1] === '*') {
        dp[i][j] = dp[i][j - 2];
        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[n][m];
}

Tradeoff: O(n*m). Datadog-canonical: same DP shape as their tag-pattern engine.

Datadog-specific tips

Datadog grades on the two '*' transitions: 'zero use' (skip the char and *) or 'one use' (consume one if it matches). Articulate both clearly BEFORE coding. They'll probe with edge cases like '.*' matching empty.

Common mistakes

Forgetting that '*' can match ZERO of the preceding — dp[0][j] = dp[0][j-2] for *.
Mishandling '.': it's a single-char wildcard, not zero-or-more.
Off-by-one between DP index (1-indexed) and string index (0-indexed).

Follow-up questions

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

Wildcard Matching (LC 44) — '*' here matches any sequence including empty.
Datadog-style: tag-pattern matching for wildcard metric queries.
Implement '?' as alternative to '.'.

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 the dp[0][j] init loop?

Patterns like 'a*b*c*' can match the empty string. The init loop handles those cases.

How does the '*' transition work?

Two cases: skip the *-group entirely (dp[i][j-2]) or consume one matched char (dp[i-1][j], if the char matches).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →