Skip to main content

82. Regular Expression Matching

hardAsked at Salesforce

Implement regular expression matching with '.' and '*'. Salesforce uses this as a 2D-DP stress test — they grade on whether you can handle the star's variable-length match.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses regex matching in their dynamic field-validation rules.
  • Blind (2025)— Salesforce hard-level DP stretch.

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 '*', 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 pos, handle '.' / regular char (advance both) or 'x*' (try zero or more matches).

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

Tradeoff: Exponential. Must memoize.

2. 2D DP

dp[i][j] = whether s[0..i] matches p[0..j]. Transitions handle 'x*' as zero (dp[i][j-2]) or more (dp[i-1][j] if first matches).

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] === '*') {
        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: O(m*n) standard DP. The '*' case is the tricky one — match zero (dp[i][j-2]) OR one-more (dp[i-1][j]).

Salesforce-specific tips

Salesforce uses regex-like matching in their dynamic field-validation rules (custom validation expressions). They grade on whether you can articulate the dp[0][j] initialization for patterns like 'a*b*' that match empty strings. Bonus signal: discuss that this generalizes to LC 44 (wildcard matching, '*' matches any sequence).

Common mistakes

  • Forgetting to initialize dp[0][j] for patterns like 'a*' that match empty strings.
  • Treating '*' as matching zero or more of ANY char — it's the PRECEDING char.
  • Confusing '.' (single any) with '*' (multiple).

Follow-up questions

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

  • Wildcard Matching (LC 44).
  • Optimize DP to O(n) space.
  • Implement non-greedy variants.

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 dp[i][j-2] for the '*' case?

Matching '*' as zero means the preceding char-pair is ignored. j-2 skips the char and the star together.

Why dp[i-1][j] for one-more?

If the current s[i-1] matches the pre-star char, we've consumed one more of s and can try the same star again — hence j stays.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →