Skip to main content

96. Regular Expression Matching

hardAsked at Ola

Implement regex matching with '.' and '*'.

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 '.' and '*'. The match must cover the entire input string, not partial.

Constraints

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

Examples

Example 1

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

Example 2

Input
s = "mississippi", p = "mis*is*p*."
Output
false

Approaches

1. Recursive char by char

Branch on whether the next pattern char is '*'.

Time
exp
Space
O(n+m)
// raw recursion; exponential without memo

Tradeoff:

2. DP table

dp[i][j] = can s[0..i] match p[0..j]; transitions handle '.' and '*'.

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},()=>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] || ((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:

Ola-specific tips

Ola asks regex matching as a hard DP showcase; tie it to validating compressed route-pattern strings against driver-supplied trip codes.

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 Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →