02. Regular Expression Matching

Difficulty:HardPattern:2D Regex State DPTime:O(s * p)Space:O(s * p)

Given an input string s and a pattern p, implement regular expression matching with support for '.' (matches any single character) and '*' (matches zero or more of the preceding element).

How It Works & Algorithmic Design

Solves using 2D Dynamic Programming with Wildcard Expansion:

DP Table: Let dp[i][j] be boolean matching status of s[0...i-1] and p[0...j-1].
Base Case: dp[0][0] = true. Handle patterns like a*b* matching empty string s.
Matching Rules:
- If p[j-1] === s[i-1] or p[j-1] === '.': dp[i][j] = dp[i-1][j-1].
- If p[j-1] === '*':
  - Zero occurrences of preceding char: dp[i][j] = dp[i][j-2].
  - One/more occurrences (if preceding char matches s[i-1] or is '.'): dp[i][j] = dp[i][j] || dp[i-1][j].

Why This Approach Works Best

Avoids infinite backtracking loops and evaluates complex regex state graphs in $O(|s| \times |p|)$ time and space.

Example Walkthrough

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

'*' matches zero or more 'a's.

Pattern Expansion: 'a*' expands to "aa", matching string s exactly.

Valid regex match.

Output: true

Matches completely.

Answer: Regular Expression Matching implementation

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 += 2) {
    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] || (dp[i - 1][j] && (s[i - 1] === p[j - 2] || p[j - 2] === '.'));
      } else {
        dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] === p[j - 1] || p[j - 1] === '.');
      }
    }
  }
  return dp[m][n];
}

💡 Build DP match matrix evaluating single character match and asterisk wildcard expansions.

Key Takeaways

Asterisk '*' operates on the preceding character.
Two choices for '*': zero matches (dp[i][j-2]) or extension match (dp[i-1][j]).
Optimal linear-squared complexity $O(|s| \times |p|)$.