← DSA Atlas
Dedicated problem page · #44

Wildcard Matching

HardTwo-Dimensional Dynamic ProgrammingGlob-matching grid DP2D dynamic programming
Solve on LeetCode ↗
44
HardTwo-Dimensional Dynamic Programming2D dynamic programmingGlob-matching grid DP

Wildcard Matching

Given an input string s and a pattern p, return true if p matches the entire string s. The pattern supports '?', which matches any single character, and '*', which matches any sequence of characters including the empty sequence. The match must cover all of s.

Open official problem prompt ↗
In plain English

We want to know whether the glob pattern can be stretched over the entire string, treating '*' as any run and '?' as one character.

Picture it like this

Exactly like matching a shell wildcard such as *a*b against a filename: '*' can swallow any stretch of characters.

Example
Input
s = "adceb", p = "*a*b"
Output
true
Why
The first '*' matches the empty string, 'a' matches 'a', the second '*' matches "dce", and 'b' matches 'b'.
Constraints
0 <= s.length, p.length <= 2000s contains only lowercase English lettersp contains lowercase letters, '?', and '*'
Pattern lesson

See the pattern, then code

Glob-matching grid DP
Recognition clue

A '*' that matches any run of characters (not tied to a preceding element) with a required full-string match signals a 2D DP over s and p, or an equivalent greedy two-pointer scan.

↗
Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. At each cell a '*' either matches no characters (move past it in the pattern) or absorbs one more character of s (stay on the star, advance the string), and '?' or a matching literal advances both by one.

New words, made simpleKnow these before the algorithm
'?' wildcard
Matches exactly one arbitrary character.
'*' wildcard
Matches any sequence of characters, possibly empty (unlike regex, it stands alone).
Full match
The pattern must account for every character of s.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Naive recursion

Redundant recomputation makes it impractical for long strings.

Branch on '*' matching 0,1,2,... characters and recurse.

Time ExponentialSpace O(m+n)
Best choice2D bottom-up DP

Clear and always correct; the recommended solution (a greedy scan can reach O(1) space but is trickier).

Prefix table with '*' handled by an OR of 'absorb one char' and 'match empty'.

Time O(m*n)Space O(m*n)
The rule we keep true

Invariant

dp[i][j] is true exactly when pattern prefix p[:j] matches string prefix s[:i].

Why this is correct

Reasoning

A non-star token reduces to the diagonal because it must consume one specific character. A '*' either matches the empty string (advance the pattern, dp[i][j-1]) or matches at least one character (consume s[i-1] and stay on the star, dp[i-1][j]); these two cases are disjoint and exhaustive, so the OR is complete and induction over prefixes proves correctness.

The algorithm in three movesSay these aloud before coding
1Define dp[i][j] = does p[:j] match s[:i]

*1 -> ""

2Seed dp[0][j] = dp[0][j-1] while p[:j] is all '*'

a -> 'a'

3On '*': dp[i][j] = dp[i-1][j] (absorb a char) OR dp[i][j-1] (match empty)

*2 -> "dce"

4On '?' or a literal match: dp[i][j] = dp[i-1][j-1]

b -> 'b'

5Return dp[m][n]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
*0
a1
*2
b3
1 · Reads='', p='*...'
2 · AskCan a leading '*' match empty?
3 · Update statedp[0][1] = dp[0][0] = True
4 · ResultTrue
Key takeaway

How each pattern token maps onto a slice of adceb.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5-7Leading stars

    A run of '*' at the pattern start can match the empty string, so seed dp[0][j] from dp[0][j-1].

  2. 2
    Lines 11-12Star: two choices

    dp[i-1][j] absorbs one more character; dp[i][j-1] matches the empty sequence.

  3. 3
    Lines 13-14Question mark or literal

    '?' or an equal character consumes exactly one char via the diagonal.

  4. 4
    Lines 15Return

    dp[m][n] reports whether the whole pattern matched the whole string.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Empty pattern matches only empty s
  • Pattern of a single '*' matches any s including empty
  • Multiple consecutive '*' behave like one
!

Common beginner mistakes

  • Confusing this '*' with regex '*' that needs a preceding element (problem 10)
  • Forgetting the empty-string branch dp[i][j-1] for '*'
  • Only seeding dp[0][0] and missing leading-star base cases
Check your understanding

How does wildcard '*' differ from the '*' in problem 10 (Regular Expression Matching)?

More in Two-Dimensional Dynamic Programming

#1143Longest Common SubsequenceSequence-alignment grid DP#72Edit DistanceSequence-alignment grid DP#10Regular Expression MatchingPattern-matching grid DP with star lookback#62Unique PathsGrid path-counting DP#63Unique Paths IIGrid path-counting DP with obstacles#64Minimum Path SumGrid path DP (right/down accumulation)