95. Regular Expression Matching

Q: Why two cases for '*'?

'a*' matches zero a's (skip 'a*' entirely, dp[i][j-2]) or one+ (eat one s char, retain 'a*', dp[i-1][j]). Take the OR.

Q: Why dp[0][j] initialization?

Empty s can match patterns like 'a*b*c*'. Pattern positions 2, 4, 6 with '*' get true if the preceding dp[0][j-2] was true.

hardAsked at Workday

Implement regex matching with '.' and '*'. Workday uses this for 2D DP with branching choice — same shape as evaluating wildcard-based permission patterns against role strings.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

Glassdoor (2026-Q1)— Workday RBAC team — wildcard matching analogy.

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

Example 2

Input

s = "aa", p = "a*"

Output

true

Example 3

Input

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

Output

true

Approaches

1. Recursive without memo

At each step, handle '*' (zero or more) and direct match.

Time: O(exponential)
Space: O(s+p)

// exponential without memo

Tradeoff: Too slow.

2. 2D DP

dp[i][j] = true if s[..i] matches p[..j]. Transitions: '*' case (zero or one+ uses).

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];
        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: 2D DP. The '*' has two cases: zero use (skip pattern) or one+ use (consume s, keep pattern).

Workday-specific tips

Workday wants the 2D DP with explicit case-handling for '*'. Walk through the two '*' cases: zero (dp[i][j-2]) and one+ (dp[i-1][j] if preceding matches s[i-1]). Articulate both before coding.

Common mistakes

Forgetting the dp[0][j] initialization for patterns like 'a*' that match empty.
Conflating '*' with '+' — '*' allows zero matches.
Forgetting that '.' matches any single character but doesn't match empty.

Follow-up questions

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

Wildcard Matching (LC 44) — '*' is multi-character.
Implement strStr (LC 28) — no wildcards.
What if there are character classes?

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 two cases for '*'?

'a*' matches zero a's (skip 'a*' entirely, dp[i][j-2]) or one+ (eat one s char, retain 'a*', dp[i-1][j]). Take the OR.

Why dp[0][j] initialization?

Empty s can match patterns like 'a*b*c*'. Pattern positions 2, 4, 6 with '*' get true if the preceding dp[0][j-2] was true.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →