Wildcard Matching
Hard · Dynamic Programming · String · Dynamic Programming · Greedy · Recursion
Problem
Given a string s and a pattern p, return true if the pattern matches the whole of s (not just part of it), and false otherwise.
The pattern has two special characters:
- '?' matches exactly one character, whatever it is.
- '*' matches any sequence of characters, including the empty one.
Every other character of the pattern matches only itself.
Examples
Input: s = "database", p = "d*b?se" Output: true
The star absorbs "ata" and the question mark matches "a".
Input: s = "abc", p = "a?" Output: false
The pattern covers exactly two characters, but the string has three.
Input: s = "", p = "***" Output: true
Every star matches the empty sequence.
Constraints
- 0 <= len(s), len(p) <= 2000
- s contains only lowercase English letters
- p contains only lowercase English letters, '?' and '*'
Approaches
- Table over prefixes — time O(|s| · |p|), space O(|s| · |p|)
Follow-up
The greedy walk is O(|s| + |p|) on most inputs but can revisit characters: a pattern like *aaaab against a long run of as makes the last star retry many starting points, O(|s| · |p|) in the worst case, the same as the table. If a pattern is used against many strings, split it at the stars into literal pieces and find each piece in order with a string search such as KMP; that gives a linear-time match.
Related problems
Start free on Cariara · Coding problems · System design studio
