Skip to main content

25. Regular Expression Matching

hardAsked at Udemy

Implement regex matching with '.' and '*' — Udemy uses 2D DP here to assess dynamic programming depth in candidates targeting search and content filtering roles.

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

Problem

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). The matching must cover the entire input string.

Constraints

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s contains only lowercase letters
  • p contains only lowercase letters, '.', and '*'

Examples

Example 1

Input
s = "aa", p = "a*"
Output
true

Example 2

Input
s = "ab", p = ".*"
Output
true

Approaches

1. Recursive without memoization

Recurse based on '*' lookahead — exponential without caching.

Time
O(2^(m+n))
Space
O(m+n)
function isMatch(s, p) {
  if (!p) return !s;
  const first = s && (p[0] === '.' || p[0] === s[0]);
  if (p[1] === '*') return isMatch(s, p.slice(2)) || (first && isMatch(s.slice(1), p));
  return first && isMatch(s.slice(1), p.slice(1));
}

Tradeoff:

2. 2D DP table

Let dp[i][j] = true if s[0..i-1] matches p[0..j-1]; fill bottom-up handling '*' by either zeroing out its pair (zero occurrences) or extending the match (one or more occurrences).

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

Tradeoff:

Udemy-specific tips

Udemy asks about e-learning recommendation systems, content search, and marketplace algorithms — balanced mix of arrays, hash maps, and dynamic programming problems.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →