44. Wildcard Matching
Asked at Atlassian, Walmart
Difficulty
Hard
Time
O(n * m)
Space
O(n * m) (can be reduced to O(m)
Pattern
String
Companies
2
Problem
You are given a string s and a pattern p. The pattern may contain normal lowercase letters, plus two special symbols:
?matches exactly one character (any character).*matches any sequence of characters, including an empty sequence.
Return true if the pattern matches the whole string s, and false otherwise. A partial match is not enough — every character of s must be consumed, and every part of p must be used up.
A useful way to think about it: * is greedy by nature, but it can also match nothing. So * at the end of a pattern can absorb any leftover characters, and * in the middle can stretch or shrink to make the rest of the pattern line up.
What the pattern symbols mean
Constraints
- ●
0 <= s.length, p.length <= 2000 - ●
s contains only lowercase English letters. - ●
p contains only lowercase English letters, '?' or '*'.
Examples
s = "aa", p = "a"falses = "aa", p = "*"trues = "cb", p = "?a"falseAsked At
2 companies| Company | Difficulty | |
|---|---|---|
| Atlassian | Hard | View all Atlassian questions → |
| Walmart | Hard | View all Walmart questions → |
How to Think About It
DP approach: dp[i][j] = true if s[0..i-1] matches p[0..j-1]. For each cell: if p[j-1] == s[i-1] or p[j-1] == ?, dp[i][j] = dp[i-1][j-1]. If p[j-1] == *, dp[i][j] = dp[i][j-1] (match empty) OR dp[i-1][j] (match one more char).
Greedy two-pointer approach: advance both pointers. On ? or exact match, advance both. On *, record the positions (star pattern position and the current s position) and try matching the star with 0 characters first (advance pattern). On mismatch, backtrack to the last * and try matching one more character.
Why greedy can be faster: in the best case O(n+m), no DP table needed. But the worst case is still O(n*m) due to backtracking. DP guarantees O(n*m) without backtracking overhead.
Complexity: both approaches are O(n*m) time and O(n*m) space (DP can be optimized to O(m) with rolling array). The greedy approach uses O(1) space but has the same worst-case time.
Optimal Approach
DP: create a 2D boolean table dp where dp[i][j] = true if s[0..i-1] matches p[0..j-1]. Initialize dp[0][0] = true. For each p[j-1] == *, dp[0][j] = dp[0][j-1] (match empty string).
For each cell (i,j):
- If p[j-1] ==
*: dp[i][j] = dp[i][j-1] (match empty) OR dp[i-1][j] (match one more char from s). - If p[j-1] ==
?or p[j-1] == s[i-1]: dp[i][j] = dp[i-1][j-1]. - Otherwise: dp[i][j] = false.
Walkthrough with s = "cb", p = "?a":
- dp[0][0] = true. dp[0][1] = false (
?cannot match empty). - dp[1][1]: p[0]=
?, s[0]=c. Match. dp[1][1] = dp[0][0] = true. - dp[1][2]: p[1]=a, s[0]=c. No match. dp[1][2] = false.
- Result: dp[2][2] = false. No match.
Time: O(n*m). Space: O(n*m) (or O(m) with rolling array).
DP table for s = "adceb", p = "*a*b"
What Trips People Up in Real Interviews
Misunderstanding * semantics. * matches zero or more of ANY character, not zero or more of the PREVIOUS character. a*b matches "ab", "axxb", "abbb" etc.
Greedy without backtracking: if you just advance past * without recording positions, you miss cases where the * needs to match more characters later. Always save the star position and s position for backtracking.
DP base cases: dp[0][0] = true (empty matches empty). For pattern *a*, dp[0][j] depends on whether p[j-1] is * — consecutive * still match empty. Initialize the first row correctly.
Forgetting to collapse consecutive * in the pattern. Multiple * in a row are equivalent to one *. This optimization reduces the pattern length but is not required for correctness.
Off-by-one errors in the DP table. dp[i][j] represents s[0..i-1] matching p[0..j-1], so the character indices are i-1 and j-1. Mixing up 0-indexed and 1-indexed causes subtle bugs.
Solution Code
O(n * m) timedef isMatch(s, p):
n, m = len(s), len(p)
dp = [[False] * (m + 1) for _ in range(n + 1)]
dp[0][0] = True
for j in range(1, m + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
for i in range(1, n + 1):
for j in range(1, m + 1):
if p[j - 1] == '*':
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif p[j - 1] == '?' or p[j - 1] == s[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[n][m]Frequently Asked Questions
What is the Wildcard Matching problem?
Given a string s and a pattern p with `?` (matches any single character) and `*` (matches any sequence of characters including empty), implement pattern matching. This problem tests your ability to handle complex string DP or two-pointer greedy optimization.
How do you solve Wildcard Matching?
The optimal approach runs in O(n * m) time and O(n * m) (can be reduced to O(m) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Wildcard Matching?
Wildcard Matching is asked at Atlassian, Walmart. It is a hard difficulty problem.
What are common mistakes on Wildcard Matching?
- Misunderstanding `*` semantics. `*` matches zero or more of ANY character, not zero or more of the PREVIOUS character. `a*b` matches "ab", "axxb", "abbb" etc.
- Greedy without backtracking: if you just advance past `*` without recording positions, you miss cases where the `*` needs to match more characters later. Always save the star position and s position for backtracking.
- DP base cases: `dp[0][0]` = true (empty matches empty). For pattern `*a*`, `dp[0][j]` depends on whether `p[j-1]` is `*` — consecutive `*` still match empty. Initialize the first row correctly.
- Forgetting to collapse consecutive `*` in the pattern. Multiple `*` in a row are equivalent to one `*`. This optimization reduces the pattern length but is not required for correctness.
- Off-by-one errors in the DP table. `dp[i][j]` represents s[0..i-1] matching p[0..j-1], so the character indices are i-1 and j-1. Mixing up 0-indexed and 1-indexed causes subtle bugs.