How do you solve Regular Expression Matching?

Use a top-down recursive DP with memoization keyed by (i, j), representing the current indices in s and p. For each state, check if the next character in p is '*'. If so, recursively check two branches: skipping the '*' and its preceding character, or if the current characters match, consuming one character from s and continuing with the same pattern index. If no '*', match the current characters and recurse forward. Cache all results to ensure each state is computed once, yielding polynomial time complexity.

What pattern does Regular Expression Matching use?

The Pattern: Dynamic Programming (Top-Down Memoization for Pattern Matching) The Heuristic: When a problem involves matching with wildcards and repetition operators, model the problem as a state machine over indices and cache results for each state to avoid exponential recomputation caused by branching.

Regular Expression Matching

Q: What is the time complexity of Regular Expression Matching?

O(m * n). There are at most m * n unique states, where m and n are the lengths of s and p respectively. Each state is computed once and cached, and each computation does O(1) work plus recursive calls to other states.

Problem

Given a string s and a pattern p, return true if s matches p, where p supports '.' matching any single character and '*' matching zero or more of the preceding element.

0 ≤ s.length ≤ 20
0 ≤ p.length ≤ 30
s contains only lowercase English letters
p contains only lowercase English letters, '.' and '*'
It is guaranteed for each appearance of '*', there will be a valid preceding character

Example

Input: s = "aab", p = "c*a*b"

Output: true

The pattern 'c*' can match zero 'c's, so it is ignored. Then 'a*' matches two 'a's in 'aab'. Finally, 'b' matches the last character 'b'. Thus, the entire string matches the pattern.

Approach

Straightforward Solution

A naive recursive solution tries all possible ways to match the pattern against the string, leading to exponential time complexity due to repeated computations and branching on '*'. This approach is infeasible for longer inputs.

Core Observation

Matching a string against a pattern with '.' and '*' can be broken down into subproblems defined by the current indices in s and p. The '*' operator introduces branching: it can either match zero occurrences of the preceding element or consume one character if it matches. This creates overlapping subproblems that can be cached.

Path to Optimal

Preview

The key recognition signals are 'pattern matching with wildcards', 'zero or more repetitions', and 'full string coverage'. These indicate Dynamic Programming because the problem breaks down into overlapping subproblems defined by indices in s and p…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a top-down recursive DP with memoization keyed by (i, j), representing the current indices in s and p. For each state, check if the next character in p is '*'…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n)

There are at most m * n unique states, where m and n are the lengths of s and p respectively. Each state is computed once and cached, and each computation does O(1) work plus recursive calls to other states.

Space

O(m * n)

The memoization dictionary stores results for each (i, j) state, requiring O(m * n) auxiliary space. The recursion stack depth is at most O(m + n), which is bounded by O(m * n).

Solution

Python

1class Solution:
  def isMatch(self, s: str, p: str) -> bool:
      memo = {}
      
      def dp(i, j):
          if (i, j) in memo:
              return memo[(i, j)]
          if j == len(p):
              return i == len(s)
          
          first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')
          
          if (j + 1) < len(p) and p[j + 1] == '*':
              res = (dp(i, j + 2) or 
                     (first_match and dp(i + 1, j)))
          else:
              res = first_match and dp(i + 1, j + 1)
          
          memo[(i, j)] = res
          return res
21
      return dp(0, 0)

Step-by-Step Solution

1

Cache Recursive Results to Avoid Redundant Computation

3memo = {}
5def dp(i, j):
6    if (i, j) in memo:
7        return memo[(i, j)]

Objective

To store the results of subproblems identified by indices (i, j) in a memo dictionary to prevent repeated work.

Key Insight

The recursive matching function explores overlapping subproblems due to the '*' operator's branching. By caching the boolean result for each (i, j) pair, the algorithm avoids exponential recomputation, ensuring each state is solved once. This memoization transforms the naive recursion into efficient dynamic programming.

Interview Quick-Check

Core Logic

Memoization keyed by (i, j) ensures that each unique substring and subpattern pair is evaluated once, preventing exponential blowup.

Common Pitfalls & Bugs

Failing to memoize leads to repeated exploration of the same states, causing timeouts on larger inputs.

2

Handle Base Case When Pattern is Exhausted

To determine if the entire string has been matched when the pattern is fully consumed.

3

Check Current Character Match with Support for Wildcard '.'

To verify if the current characters in s and p match, considering '.' as a wildcard.

4

Branch on '*' Operator to Explore Zero or More Matches

To handle the '*' operator by recursively exploring skipping it or consuming matching characters.

5

Advance Both String and Pattern Indices on Direct Match

To move forward in both s and p when the current characters match and no '*' follows.

6

Memoize and Return the Computed Result for Current State

To store the computed boolean result for the current (i, j) state and return it.

7

Initiate Recursive Matching from Start of Strings

To start the recursive matching process from the beginning of s and p.

6 more steps with full analysis available on Pro.

Line Analysis

This solution has 8 Critical lines interviewers watch for.

Line 6 Critical

if (i, j) in memo:

Check if the current state (i, j) has been computed before.

This lookup prevents redundant work by returning cached results, a cornerstone of top-down DP.

Line 7 Critical

return memo[(i, j)]

Return the cached result for the current state if available.

Returning cached results immediately prunes the recursion tree, ensuring polynomial time complexity.

Line 3 Critical

memo = {}

Initialize a memoization dictionary to cache subproblem results.

Memoization is essential to avoid exponential recomputation by storing results of each (i, j) state, enabling efficient dynamic programming.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why does memoizing the results of subproblems defined by indices (i, j) prevent exponential time complexity?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Regular Expression Matching from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Regular Expression Matching drill

or drill a free problem

1	`class Solution:`
2	`def isMatch(self, s: str, p: str) -> bool:`
3	`memo = {}`
4
5	`def dp(i, j):`
6	`if (i, j) in memo:`
7	`return memo[(i, j)]`
8	`if j == len(p):`
9	`return i == len(s)`
10
11	`first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')`
12
13	`if (j + 1) < len(p) and p[j + 1] == '*':`
14	`res = (dp(i, j + 2) or`
15	`(first_match and dp(i + 1, j)))`
16	`else:`
17	`res = first_match and dp(i + 1, j + 1)`
18
19	`memo[(i, j)] = res`
20	`return res`
21
22	`return dp(0, 0)`

3	`memo = {}`
5	`def dp(i, j):`
6	`if (i, j) in memo:`
7	`return memo[(i, j)]`