What is the brute force approach and complexity for Regular Expression Matching?

Recurse on (i, j): a starred pair takes zero copies, or one more copy of its letter with time complexity O(2^(N + M)) and space complexity O(N + M).

What is the optimal approach and complexity for Regular Expression Matching?

Keep one row over the pattern; a star reads the new cell two back and the old cell above with optimal time complexity O(N · M) and space complexity O(M).

How do you identify the pattern for Regular Expression Matching?

Look for key signals in the prompt: ". matches any one character" indicates A letter that matches any letter. The diagonal rule applies to it.; "x* means zero or more of x" indicates The star belongs to the character before it. The pair is one unit with two choices.; "matches the entire input" indicates A full match. The answer is the last cell of the table, not the best cell..

Regular Expression Matching

Hard·LeetCode #10 Pro OnlyTricky / Edge Case

LeetCode

Problem Statement

You get a string s and a pattern p. Decide whether the pattern matches the whole string.

The pattern uses two special characters. . matches any one letter. x* means zero or more copies of x, where x is the letter or . just before the star. A star belongs only to the character right before it.

Input

A string s and a pattern p.

Output

true if p matches all of s, otherwise false.

Example 1

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

Output: false

a matches only one letter, and s has two.

Example 2

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

Output: true

a* means zero or more a's. Here it takes both letters.

Example 3

Input: s = "ab", p = ".*"

Output: true

. matches any letter, and the star repeats it. So .* matches any string.

Constraints

• 1 ≤ s.length ≤ 20
• 1 ≤ p.length ≤ 20
• s contains only lowercase English letters.
• p contains only lowercase English letters, `.` and `*`.
• Every `*` has a valid character before it to repeat.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“. matches any one character”

→ A letter that matches any letter. The diagonal rule applies to it.

“x* means zero or more of x”

→ The star belongs to the character before it. The pair is one unit with two choices.

“matches the entire input”

→ A full match. The answer is the last cell of the table, not the best cell.

Approach Complexity Ladder

Brute Force — zero copies or one more copy of each starO(2^(N + M))O(N + M)

Recurse on (i, j): a starred pair takes zero copies, or one more copy of its letter

Better — 2D table dp[i][j], one cell per pair of prefixesO(N · M)O(N · M)

dp[i][j] = does the first j pattern characters match the first i letters of s, each cell once

Optimal — one row, reading the new value two cells backO(N · M)O(M)

Keep one row over the pattern; a star reads the new cell two back and the old cell above

Brute Force Intuition

Let match(i, j) say whether the first j pattern characters match the first i characters of s. If the last pattern character is a star, the pair x* before it is one choice. Zero copies skips both characters: match(i, j − 2). One more copy needs x to match s[i − 1], and then the star stays for more copies: match(i − 1, j). Any other character matches one letter, as usual.

Recognition rule for this sub-pattern:

Each cell picks the cheapest of insert / delete / replace (or the pattern rule for *, ?, .).

Remember this · DP — Strings

Trigger

Longest common subsequence, edit distance, palindromes, matching with wildcards, interleaving.

Think

Look at the last characters: if they match, what do I do? If not, what are my options?

Key question

What does dp[i][j] mean, and what are the empty-string base cases?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Strings translate into production architectures and low-level memory mechanics.

LLD Architecture