Wildcard Matching
Asked at Atlassian, Walmart
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.
Asked At
| 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).
Visual walkthrough for s = "adceb", p = "*a*b":
dp matrix (rows=s, cols=p):
"" * a * b
"" T T F F F
a F T T T F
d F T F T F
c F T F T F
e F T F T F
b F T F T T
Result: dp[5][4] = true
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).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.