Wildcard Matching
Wildcard Matching: match an entire string against a pattern where ? matches one character and * matches any sequence.
- 0 <= s.length, p.length <= 2000
- s contains only lowercase English letters.
- p contains only lowercase English letters, '?' or '*'.
Intuition
Wildcard matching tests a string against a pattern where ? matches exactly one character and * matches any sequence, including nothing. The * is what makes it hard, since it has no fixed length.
A two-dimensional DP works and is the standard answer, but there is a greedy two-pointer solution running in O(1) space, and the reasoning behind it is the interesting part.
Ordinary characters and ? have no choice — they either match in place or the attempt fails. Only * has freedom. And crucially:
- Only the most recent star ever needs reconsidering, because any earlier star's decision is already locked in by the characters matched since.
So remember where the last star appeared and how much of the string it had consumed. Walk both pointers forward through forced matches. On a mismatch, rather than abandoning everything, give the saved star one more character and resume from just after that point.
That backtracking is bounded — each mismatch extends the star's span by one, and the string pointer only moves forward overall — so the walk stays near-linear rather than exponential.
One detail decides correctness at the end: after the string is exhausted, any remaining pattern characters must all be stars. A leftover ? or literal means the pattern demands more input than exists.
Wildcard matching differs from regex: ** stands alone and matches arbitrary characters. With only ? and **, a linear greedy scan can use the latest star as a controlled backtracking checkpoint.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(|s| + |p|) time and O(1) space.
Advance on forced matches
When the characters agree or the pattern has ?, advance both pointers. These matches have no alternative, so no state needs saving — the only decisions in the whole problem belong to stars.
Record the star and the string position
On reaching *, save its pattern index and the current string index, then advance past the star, initially matching zero characters. This is the retry point the algorithm returns to.
Expand the star on a mismatch
If matching fails and a star was seen, give it one more character: increment the saved string position, resume the string there, and reset the pattern to just after the star. This is the only backtracking that ever happens.
Fail when no star is available
A mismatch with no recorded star means the pattern genuinely cannot match — return false. There is nothing to reconsider, since every earlier decision was forced.
Consume trailing stars
Once the string is exhausted, skip any remaining stars in the pattern. The match succeeds only if nothing but stars remains — a leftover ? or literal requires input that does not exist.
Know the DP alternative
A dp[i][j] table over prefix pairs also solves this at O(n·m) time and space, and is easier to argue correct. The greedy version is O(1) space, which is the reason to prefer it once you trust the last-star argument.
Cost of the greedy walk
Each mismatch advances the star's span by one and the string pointer never retreats overall, giving O(n·m) worst case but near-linear in practice, with O(1) space.
Solution & live demo
Common pitfalls
Giving wildcard star regex semantics
star repeats p[j - 1]
star matches any sequence of characters
In this problem * is an independent wildcard, not a postfix operator.
Retrying from the star itself
j = star
j = star + 1
The saved star already absorbs the expanded substring; matching must resume after it.
Rejecting leftover stars
return j == len(p)
while j < len(p) and p[j] == '*':
j += 1
return j == len(p)A trailing star may match the empty sequence.
Edge cases
The final cleanup skips every star and accepts.
Each is recorded and skipped; their combined behavior is equivalent to one star.
There is no flexible token to adjust, so return false immediately.