Wildcard Matching (LeetCode 44)
You're given a text string s and a wildcard pattern p built from ordinary characters plus two special symbols: '?', standing in for any one character, and '*', standing in for any run of characters, including an empty one.
Decide whether p matches s from the first character all the way to the last -- a partial match doesn't count.
Worked Examples
s = "aa", p = "a"falses = "aa", p = "*"trues = "cb", p = "?a"false⚖️Formal Constraints & Bounds
0 <= s.length, p.length <= 2000scontains only lowercase English letters.pcontains only lowercase English letters,'?'or'*'.
Core Insight
'*' must check TWO transitions simultaneously -- 'consume one more source character and stay on the same * ' (dp[i-1][j]) or 'match the empty sequence and move past the ' (dp[i][j-1]) -- while the base row only stays True through a leading run of '' characters.
Real-World Scenario & Production Applications
Shell glob-style filename matching (*.txt, report_?.csv), search-box wildcard filters.
Subproblems & Recurrence Decomposition3 Phases
Define dp[i][j] as True iff s[:i] fully matches p[:j]. The empty string only matches a pattern prefix consisting entirely of '*' characters, so the base row stays True only through a leading run of '*'.
dp = [[False] * (N + 1) for _ in range(M + 1)]
dp[0][0] = True
for j in range(1, N + 1):
dp[0][j] = dp[0][j - 1] if p[j - 1] == '*' else FalseStep-by-Step Execution Trace Table
| s prefix | p prefix | Rule Applied | dp Cell Value |
|---|---|---|---|
| "" | "" | Base case | True |
| "a" | "*" | '*' matches empty (dp[0][0]) | True |
| "ad" | "ab*" | '*' consumes one more char (dp[i-1][j]) | True |
| "adceb" | "ab*" | Final cell: full match | True |
| 1 | dp = [[False]*(n+1) for _ in range(m+1)] |
| 2 | dp[0][0] = True |
| 3 | for j in range(1, n + 1): |
| 4 | dp[0][j] = dp[0][j-1] if p[j-1] == '*' else False |
| 5 | for i in range(1, m + 1): |
| 6 | for j in range(1, n + 1): |
| 7 | if p[j-1] in ('?', s[i-1]): |
| 8 | dp[i][j] = dp[i-1][j-1] |
| 9 | elif p[j-1] == '*': |
| 10 | dp[i][j] = dp[i-1][j] or dp[i][j-1] |
| 11 | else: |
| 12 | dp[i][j] = False |
| 13 | return dp[m][n] |
Conceptual Narrative
Wildcard Matching is a harder Dual Sequence DP problem: the pattern language has only two symbols ('?' and ''), but the recurrence has a subtle trap around consecutive '' characters.
🧭 Conceptual Foundation & Pattern Intuition
Unlike Edit Distance where every cell picks the cheapest of three fixed operations, Wildcard Matching's grid answers a yes/no question: "can pattern prefix p[:j] match string prefix s[:i]?" The '?' character is trivial -- it behaves exactly like a guaranteed literal match, consuming one character from each side and inheriting the diagonal cell. The '' character is where the trap lives: it can match a sequence of any length, including zero, so cell (i, j) must ask two different questions simultaneously -- "does '' consume this source character and still match?" (dp[i-1][j]) OR "does '*' match nothing at all here?" (dp[i][j-1]).
🌟 The Analogy: A Rubber Band Wildcard
Think of '' as a stretchy rubber band that can shrink to zero width or stretch to cover any number of source characters. At each grid cell touching a '', you ask: "could I let the rubber band stretch one more character to the left (dp[i-1][j], keep the same '' and let it cover one more source character) or could I let the rubber band snap all the way to zero width right here (dp[i][j-1], move past the '' entirely)?" If either is true, the cell is true.
🔑 The Key Idea in the Code
The base row dp[0][j] is the classic trap: since '' can match empty, a pattern of ALL '' characters (e.g. "***") can still match the empty string, so dp[0][j] = dp[0][j-1] only while every preceding pattern character is '' -- the first non-'' character permanently zeroes out that row.
Leading pattern asterisks base case: Only setting
dp[0][0] = Trueand failing to account for leading*in the pattern. A pattern like****matches an empty string"". Setdp[0][j] = dp[0][j-1]whilep[j-1] == '*'.*dual-transition omission: Implementing*as only matching empty or only matching a single character. An asterisk matches empty (dp[i][j-1]) OR extends to match one more character (dp[i-1][j]). Both branches must be OR'd:dp[i][j] = dp[i][j-1] or dp[i-1][j].?wildcard character mismatch: Treating?as matching zero or more characters.?strictly matches exactly one arbitrary character; it cannot match an empty string.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Boolean full-string match against a pattern containing '?' (any one char) and '*' (any sequence, including empty).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: dp[i][j] is True iff s[:i] can be fully matched by p[:j].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting the base row: dp[0][j] stays True only through a leading run of consecutive '*' characters, then permanently False.
Only checking dp[i-1][j-1] for '*' instead of the two-way OR of dp[i-1][j] (consume) and dp[i][j-1] (match empty).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I build an
(m+1) x (n+1)boolean grid withdp[0][0] = True. The base row handles leading '' runs:dp[0][j] = dp[0][j-1]only whilep[j-1] == '*'. For each cell, '?' or a literal match inheritsdp[i-1][j-1]; '' is True if eitherdp[i-1][j](consume one more source char) ordp[i][j-1](match empty) is True. Runs in O(M · N) time and O(M · N) space."
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: 2D boolean DP table for string s of length M and pattern p of length N. Each cell does O(1) work: either inherit a diagonal, or OR two neighboring cells for '*'.
O(M · N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Full (M+1) x (N+1) boolean grid retained (can be rolled to O(N) with two 1D rows).
T(M, N) = M · N = O(M · N)
Derivation Progression
dp[i][j] = dp[i-1][j-1]
O(1) diagonal inheritance when characters match or pattern char is '?'.
dp[i][j] = dp[i-1][j] or dp[i][j-1]
O(1) OR of 'consume one more source char' and 'match empty sequence'.
O(M · N) total cells
Every cell computed exactly once in row-major order.
Variable Definitions
Length of the input string s
Length of the pattern p
Memory Architecture & Bounds
O(1) Iterative
O(M · N) boolean grid (or O(N) with rolling rows)
O(1) boolean result
Boundary Best / Worst Cases
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "'?' matches single char", "'*' matches any sequence of chars". 2D boolean matching table: - If : dp[i][j] = dp[i-1][j] (star absorbs current character) or dp[i][j-1] (star matches empty sequence). - If or matches char: dp[i][j] = dp[i-1][j-1].
. Budget .
Wildcard Matching (LeetCode 44)
You're given a text string s and a wildcard pattern p built from ordinary characters plus two special symbols: '?', standing in for any one character, and '*', standing in for any run of characters, including an empty one.
Decide whether p matches s from the first character all the way to the last -- a partial match doesn't count.
Worked Examples
s = "aa", p = "a"falses = "aa", p = "*"trues = "cb", p = "?a"false⚖️Formal Constraints & Bounds
0 <= s.length, p.length <= 2000scontains only lowercase English letters.pcontains only lowercase English letters,'?'or'*'.
Core Insight
'*' must check TWO transitions simultaneously -- 'consume one more source character and stay on the same * ' (dp[i-1][j]) or 'match the empty sequence and move past the ' (dp[i][j-1]) -- while the base row only stays True through a leading run of '' characters.
Real-World Scenario & Production Applications
Shell glob-style filename matching (*.txt, report_?.csv), search-box wildcard filters.
Subproblems & Recurrence Decomposition3 Phases
Define dp[i][j] as True iff s[:i] fully matches p[:j]. The empty string only matches a pattern prefix consisting entirely of '*' characters, so the base row stays True only through a leading run of '*'.
dp = [[False] * (N + 1) for _ in range(M + 1)]
dp[0][0] = True
for j in range(1, N + 1):
dp[0][j] = dp[0][j - 1] if p[j - 1] == '*' else FalseStep-by-Step Execution Trace Table
| s prefix | p prefix | Rule Applied | dp Cell Value |
|---|---|---|---|
| "" | "" | Base case | True |
| "a" | "*" | '*' matches empty (dp[0][0]) | True |
| "ad" | "ab*" | '*' consumes one more char (dp[i-1][j]) | True |
| "adceb" | "ab*" | Final cell: full match | True |
| 1 | dp = [[False]*(n+1) for _ in range(m+1)] |
| 2 | dp[0][0] = True |
| 3 | for j in range(1, n + 1): |
| 4 | dp[0][j] = dp[0][j-1] if p[j-1] == '*' else False |
| 5 | for i in range(1, m + 1): |
| 6 | for j in range(1, n + 1): |
| 7 | if p[j-1] in ('?', s[i-1]): |
| 8 | dp[i][j] = dp[i-1][j-1] |
| 9 | elif p[j-1] == '*': |
| 10 | dp[i][j] = dp[i-1][j] or dp[i][j-1] |
| 11 | else: |
| 12 | dp[i][j] = False |
| 13 | return dp[m][n] |
Conceptual Narrative
Wildcard Matching is a harder Dual Sequence DP problem: the pattern language has only two symbols ('?' and ''), but the recurrence has a subtle trap around consecutive '' characters.
🧭 Conceptual Foundation & Pattern Intuition
Unlike Edit Distance where every cell picks the cheapest of three fixed operations, Wildcard Matching's grid answers a yes/no question: "can pattern prefix p[:j] match string prefix s[:i]?" The '?' character is trivial -- it behaves exactly like a guaranteed literal match, consuming one character from each side and inheriting the diagonal cell. The '' character is where the trap lives: it can match a sequence of any length, including zero, so cell (i, j) must ask two different questions simultaneously -- "does '' consume this source character and still match?" (dp[i-1][j]) OR "does '*' match nothing at all here?" (dp[i][j-1]).
🌟 The Analogy: A Rubber Band Wildcard
Think of '' as a stretchy rubber band that can shrink to zero width or stretch to cover any number of source characters. At each grid cell touching a '', you ask: "could I let the rubber band stretch one more character to the left (dp[i-1][j], keep the same '' and let it cover one more source character) or could I let the rubber band snap all the way to zero width right here (dp[i][j-1], move past the '' entirely)?" If either is true, the cell is true.
🔑 The Key Idea in the Code
The base row dp[0][j] is the classic trap: since '' can match empty, a pattern of ALL '' characters (e.g. "***") can still match the empty string, so dp[0][j] = dp[0][j-1] only while every preceding pattern character is '' -- the first non-'' character permanently zeroes out that row.
Leading pattern asterisks base case: Only setting
dp[0][0] = Trueand failing to account for leading*in the pattern. A pattern like****matches an empty string"". Setdp[0][j] = dp[0][j-1]whilep[j-1] == '*'.*dual-transition omission: Implementing*as only matching empty or only matching a single character. An asterisk matches empty (dp[i][j-1]) OR extends to match one more character (dp[i-1][j]). Both branches must be OR'd:dp[i][j] = dp[i][j-1] or dp[i-1][j].?wildcard character mismatch: Treating?as matching zero or more characters.?strictly matches exactly one arbitrary character; it cannot match an empty string.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Boolean full-string match against a pattern containing '?' (any one char) and '*' (any sequence, including empty).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: dp[i][j] is True iff s[:i] can be fully matched by p[:j].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting the base row: dp[0][j] stays True only through a leading run of consecutive '*' characters, then permanently False.
Only checking dp[i-1][j-1] for '*' instead of the two-way OR of dp[i-1][j] (consume) and dp[i][j-1] (match empty).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I build an
(m+1) x (n+1)boolean grid withdp[0][0] = True. The base row handles leading '' runs:dp[0][j] = dp[0][j-1]only whilep[j-1] == '*'. For each cell, '?' or a literal match inheritsdp[i-1][j-1]; '' is True if eitherdp[i-1][j](consume one more source char) ordp[i][j-1](match empty) is True. Runs in O(M · N) time and O(M · N) space."
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: 2D boolean DP table for string s of length M and pattern p of length N. Each cell does O(1) work: either inherit a diagonal, or OR two neighboring cells for '*'.
O(M · N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Full (M+1) x (N+1) boolean grid retained (can be rolled to O(N) with two 1D rows).
T(M, N) = M · N = O(M · N)
Derivation Progression
dp[i][j] = dp[i-1][j-1]
O(1) diagonal inheritance when characters match or pattern char is '?'.
dp[i][j] = dp[i-1][j] or dp[i][j-1]
O(1) OR of 'consume one more source char' and 'match empty sequence'.
O(M · N) total cells
Every cell computed exactly once in row-major order.
Variable Definitions
Length of the input string s
Length of the pattern p
Memory Architecture & Bounds
O(1) Iterative
O(M · N) boolean grid (or O(N) with rolling rows)
O(1) boolean result
Boundary Best / Worst Cases
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "'?' matches single char", "'*' matches any sequence of chars". 2D boolean matching table: - If : dp[i][j] = dp[i-1][j] (star absorbs current character) or dp[i][j-1] (star matches empty sequence). - If or matches char: dp[i][j] = dp[i-1][j-1].
. Budget .