What is the brute force approach and complexity for Wildcard Matching?

Recurse on (i, j): the last pattern character decides the move with time complexity O(2^(N + M)) and space complexity O(N + M).

What is the optimal approach and complexity for Wildcard Matching?

Keep one row over the pattern; a star reads the cell to its left and the cell above with optimal time complexity O(N · M) and space complexity O(M).

How do you identify the pattern for Wildcard Matching?

Look for key signals in the prompt: "? matches any single character" indicates Uses exactly one letter, the same as a plain letter, except that it matches any letter.; "* matches any sequence, including empty" indicates A free choice: zero letters, or one more letter while staying on the star. This is the only decision point.; "matches the whole string" indicates A full match, so the answer is the last cell of the table, not the best cell in it..

Wildcard Matching

Hard·LeetCode #44 Pro OnlyInterview-Level

LeetCode

Problem Statement

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

The pattern can use two special characters. ? matches any one letter. * matches any sequence of letters, including the empty sequence. Every other pattern character must match the same letter in s.

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 = "*"

Output: true

* matches any sequence, so here it matches both letters.

Example 3

Input: s = "cb", p = "?a"

Output: false

? matches c, but the second pattern character is a and the string has b there.

Constraints

• 0 ≤ s.length, p.length ≤ 2000
• s contains only lowercase English letters.
• p contains only lowercase English letters, `?` or `*`.

Pattern Recognition Clues

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

“? matches any single character”

→ Uses exactly one letter, the same as a plain letter, except that it matches any letter.

“* matches any sequence, including empty”

→ A free choice: zero letters, or one more letter while staying on the star. This is the only decision point.

“matches the whole string”

→ A full match, so the answer is the last cell of the table, not the best cell in it.

Approach Complexity Ladder

Brute Force — each star matches nothing, or takes one more letterO(2^(N + M))O(N + M)

Recurse on (i, j): the last pattern character decides the move

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 characters of s, filled once per cell

Optimal — one row over the pattern, updated left to rightO(N · M)O(M)

Keep one row over the pattern; a star reads the cell to its left and the cell above

Brute Force Intuition

Let match(i, j) say whether the first j pattern characters match the first i characters of s. Look at the last pattern character. A letter or ? must match s[i − 1], and then we continue with match(i − 1, j − 1). A * either matches nothing, which is match(i, j − 1), or takes s[i − 1] and stays on the star, which is match(i − 1, j). The empty pattern matches only the empty string.

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