82. Regular Expression Matching

Q: Why two cases for '*'?

Either the preceding element doesn't appear (zero use) or it does (one or more times). Both must be tried.

Q: Why fill dp[0][j] specially?

An empty input can match patterns like 'a*b*c*' (each star matches zero of its preceding). Without seeding, the DP misses these.

hardAsked at Plaid

Implement regular expression matching with '.' and '*'. Plaid asks this because matching merchant-name patterns with wildcards is a recurring sub-problem in their pattern-based classification rules.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

Glassdoor (2025)— Plaid SWE III onsite — merchant-pattern matcher.
LeetCode Discuss (2026)— Plaid hard DP.

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 that each appearance of the character '*' is preceded by a valid character.

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

Match each character; '*' tries both zero-use and one-use branches.

Time: exponential
Space: O(m+n)

// Exponential without memo.

Tradeoff: TLE on adversarial inputs.

2. 2D DP

dp[i][j] = does s[0..i] match p[0..j]? Recurrence handles three cases: literal char, '.', '*'.

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

Tradeoff: Quadratic time and space. The '*' branch is the only subtle case: it can match zero or extend.

Plaid-specific tips

Plaid grades this on whether you handle the '*' correctly — zero-use and one-or-more-use are independent branches. Bonus signal: connect to merchant-pattern rules where a pattern like 'STARBUCKS.*' matches any merchant starting with STARBUCKS regardless of trailing tokens.

Common mistakes

Initializing dp[0][j] without skip-by-two for '*' — misses empty matches.
Forgetting the zero-use branch of '*'.
Off-by-one between dp index and string index.

Follow-up questions

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

Wildcard matching (LC 44) — '?' and '*' with different semantics.
Full PCRE — vastly harder.
Streaming regex match.

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 '*'?

Either the preceding element doesn't appear (zero use) or it does (one or more times). Both must be tried.

Why fill dp[0][j] specially?

An empty input can match patterns like 'a*b*c*' (each star matches zero of its preceding). Without seeding, the DP misses these.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →