Log inSign up
hardleetcodeNot Started

Regular Expression Matching

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

- '.' Matches any single character. - '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Example 1 · Example:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2 · Example:

Input: s = "aa", p = "a*"
Output: true
Explanation: * means zero or more of the preceding element, a. Therefore, by repeating a once, it becomes "aa".

Example 3 · Example:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

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 the character '*', there will be a previous valid character to match.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 2-choice recurrence for Kleene star repetition.
  • Formulate 2D grid DP table base cases for empty prefixes.
  • Handle . wildcard character matching.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Pattern matching with wildcard/repetition tokens (*, ?).
  • Prefix and character pair decision trees with overlapping subproblems.

Algorithmic Decision Tree:

  • 2D Grid Dynamic Programming
  • NFA State Simulation

Connected Patterns:

Wildcard MatchingEdit DistanceInterleaving String

1. Top-Down Recursion with Memoization

Intuition

Define match(i, j) returning whether s[i...] matches p[j...]. If j == p.length, return i == s.length. Check if firstMatch = (i < s.length && (s[i] == p[j] || p[j] == '.')). If j + 1 < p.length && p[j + 1] == '*': return match(i, j + 2) || (firstMatch && match(i + 1, j)). Else: return firstMatch && match(i + 1, j + 1). Memoize with memo[i][j].

When to apply: When deriving the recurrence relationship from first principles.

Algorithm

  1. Create memo matrix of size (N + 1) x (M + 1) initialized to -1.
  2. Helper dp(i, j):
  3. If j == m: return i == n.
  4. If memo[i][j] != -1: return memo[i][j].
  5. firstMatch = (i < n && (s[i] == p[j] || p[j] == '.')).
  6. If j + 1 < m && p[j + 1] == '*':
  7. ans = dp(i, j + 2) || (firstMatch && dp(i + 1, j)).
  8. Else:
  9. ans = firstMatch && dp(i + 1, j + 1).
  10. Return memo[i][j] = ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6 int memo[25][35];
7
8 bool dp(int i, int j, const std::string& s, const std::string& p) {
9 if (j == (int)p.size()) return i == (int)s.size();
10 if (memo[i][j] != -1) return memo[i][j];
11
12 bool firstMatch = (i < (int)s.size() && (s[i] == p[j] || p[j] == '.'));
13 bool ans = false;
14
15 if (j + 1 < (int)p.size() && p[j + 1] == '*') {
16 ans = dp(i, j + 2, s, p) || (firstMatch && dp(i + 1, j, s, p));
17 } else {
18 ans = firstMatch && dp(i + 1, j + 1, s, p);
19 }
20
21 return memo[i][j] = ans;
22 }
23public:
24 bool isMatch(std::string s, std::string p) {
25 for (int i = 0; i <= 24; ++i)
26 for (int j = 0; j <= 34; ++j)
27 memo[i][j] = -1;
28 return dp(0, 0, s, p);
29 }
30};
31
32int main() {
33 Solution sol;
34 std::cout << (sol.isMatch("aa", "a*") ? "true" : "false") << std::endl; // true
35 std::cout << (sol.isMatch("ab", ".*") ? "true" : "false") << std::endl; // true
36 std::cout << (sol.isMatch("aa", "a") ? "true" : "false") << std::endl; // false
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N * M) — There are (N + 1) * (M + 1) states, each evaluated in O(1).
  • Space complexity: O(N * M)

Why Brute Force Doesn't Scale:

2D Dynamic Programming table avoids exponential branching of naive backtracking.

State transitions only depend on the current and previous rows.

2. 1D Space-Optimized Rolling DP

Intuition

Maintain dp (previous row) and curr (current row) arrays of size M + 1. Initialize dp[0] = true and base cases for p[j-1] == '*'. Update row by row.

When to apply: When memory space is constrained.

Algorithm

  1. Initialize dp array of size m + 1 with false; set dp[0] = true.
  2. Set base cases for p[j - 1] == '*' on dp.
  3. For each row i from 1 to n:
  4. Create curr[m + 1] = false.
  5. For j from 1 to m:
  6. If p[j - 1] == '*': curr[j] = curr[j - 2] || ((s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[j]).
  7. Else: curr[j] = (s[i - 1] == p[j - 1] || p[j - 1] == '.') && dp[j - 1].
  8. dp = curr.
  9. Return dp[m].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 bool isMatch(std::string s, std::string p) {
8 int n = s.size(), m = p.size();
9 std::vector<bool> dp(m + 1, false);
10 dp[0] = true;
11
12 for (int j = 2; j <= m; j += 2) {
13 if (p[j - 1] == '*') dp[j] = dp[j - 2];
14 }
15
16 for (int i = 1; i <= n; ++i) {
17 std::vector<bool> curr(m + 1, false);
18 for (int j = 1; j <= m; ++j) {
19 if (p[j - 1] == '*') {
20 bool match = (s[i - 1] == p[j - 2] || p[j - 2] == '.');
21 curr[j] = curr[j - 2] || (match && dp[j]);
22 } else {
23 bool match = (s[i - 1] == p[j - 1] || p[j - 1] == '.');
24 curr[j] = match && dp[j - 1];
25 }
26 }
27 dp = std::move(curr);
28 }
29 return dp[m];
30 }
31};
32
33int main() {
34 Solution sol;
35 std::cout << (sol.isMatch("aa", "a*") ? "true" : "false") << std::endl; // true
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N * M) — Fills N rows of size M using two 1D arrays.
  • Space complexity: O(M) memory

3. Bottom-Up 2D Dynamic Programming (Optimal Standard)

Intuition

Let dp[i][j] be true if prefix s[0...i-1] matches pattern prefix p[0...j-1]. Base cases: dp[0][0] = true. For empty string s, initialize dp[0][j] = dp[0][j - 2] if p[j - 1] == '*'. For each i (1 to n) and j (1 to m): if p[j - 1] == '*': zero matches gives dp[i][j - 2]; one or more matches gives (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]. If p[j - 1] != '*': match single char (s[i - 1] == p[j - 1] || p[j - 1] == '.') && dp[i - 1][j - 1]. Answer is dp[n][m].

When to apply: The standard gold standard solution for technical interviews.

Algorithm

  1. Initialize dp[n + 1][m + 1] with false.
  2. dp[0][0] = true.
  3. For j from 2 to m: if p[j - 1] == '*': dp[0][j] = dp[0][j - 2].
  4. Loop i from 1 to n:
  5. Loop j from 1 to m:
  6. If p[j - 1] == '*':
  7. dp[i][j] = dp[i][j - 2] || ((s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]).
  8. Else:
  9. dp[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '.') && dp[i - 1][j - 1].
  10. Return dp[n][m].

2D Dynamic Programming Asterisk Wildcard Lattice

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [c, *, a, *, b]
Current operationSTEP 1 OF 6
Observation: Base case dp[0][0] = true
Visual state
Values and pointers at this exact step
array
S
c*
a*
b
0
↑ dp[0][2] = true (0 instances of 'c')
1
2
Variables at this step
emptyStringMatch
true
dp00
true
dp02
true
formula
dp[0][j] = dp[0][j-2]
Why this step matters

Observation: Base case dp[0][0] = true. For empty string s = "", pattern "c*" can match 0 occurrences of 'c'.

Decision: Set dp[0][2] = dp[0][0] = true.

Invariant: Asterisk enables matching empty prefixes by zeroing preceding character.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 bool isMatch(std::string s, std::string p) {
8 int n = s.size(), m = p.size();
9 std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(m + 1, false));
10
11 dp[0][0] = true;
12
13 for (int j = 2; j <= m; ++j) {
14 if (p[j - 1] == '*') {
15 dp[0][j] = dp[0][j - 2];
16 }
17 }
18
19 for (int i = 1; i <= n; ++i) {
20 for (int j = 1; j <= m; ++j) {
21 if (p[j - 1] == '*') {
22 bool zeroOccurrences = dp[i][j - 2];
23 bool oneOrMore = (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j];
24 dp[i][j] = zeroOccurrences || oneOrMore;
25 } else {
26 bool charMatch = (s[i - 1] == p[j - 1] || p[j - 1] == '.');
27 dp[i][j] = charMatch && dp[i - 1][j - 1];
28 }
29 }
30 }
31
32 return dp[n][m];
33 }
34};
35
36int main() {
37 Solution sol;
38 std::cout << (sol.isMatch("aa", "a*") ? "true" : "false") << std::endl; // true
39 std::cout << (sol.isMatch("ab", ".*") ? "true" : "false") << std::endl; // true
40 std::cout << (sol.isMatch("aa", "a") ? "true" : "false") << std::endl; // false
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(N * M) — Fills every cell in the (N + 1) x (M + 1) matrix in O(1) state transitions.
  • Space complexity: O(N * M)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Top-Down Recursion with MemoizationO(N * M)O(N * M) memo table + O(N + M) call stackVery intuitive code mimicking grammatical regex parsing.Recursion overhead.
2.Bottom-Up 2D Dynamic Programming (Optimal)O(N * M)O(N * M)Iterative, zero recursion overhead, robust table evaluation.Requires careful table base case setup.
3.1D Space-Optimized Rolling DPOptimalO(N * M)O(M)Minimal memory footprint.Slightly complex state management for * spanning multiple rows.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Treating * as matching any sequence like wildcard ? (in regex * applies to the preceding character).

Pitfall 2:

Missing base case initialization for dp[0][j] on patterns like a*b*.

Crucial Edge Cases to Validate:

  • Empty string matching sequence of wildcards (s="", p="a*b*c*"): Base row initialization correctly sets dp[0][j] = dp[0][j-2] = true.
  • Dot star wildcard matching arbitrary string (s="abcdef", p=".*"): oneOrMore condition with . consumes character by character, returning true.
  • Non-matching trailing character: Returns false since entire string must match.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Carefully articulate the two branches for *: 0 occurrences (dp[i][j-2]) and 1+ occurrences (match && dp[i-1][j]).
  2. Explain base row filling for empty string prefixes.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When evaluating p[j - 1] == '*' , why does the 1+ occurrences branch check dp[i - 1][j] rather than dp[i - 1][j - 2]?

Back to DSA Sheet