Log inSign up
hardleetcodeNot Started

Wildcard Matching

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

- '?' Matches any single character. - '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: * matches any sequence.

Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation: ? matches c, but the second letter is a, which does not match b.

Example 4:

Input: s = "adceb", p = "*a*b"
Output: true
Explanation: The first * matches the empty sequence, a matches a, second * matches "dce", and b matches b.

Constraints:

  • 0 <= s.length, p.length <= 2000
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '?' or '*'.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate 2D DP recurrence relations for wildcard characters.
  • Optimize 2D DP state matrix to 1D sliding rows.
  • Implement the greedy star backtracking two-pointer technique in O(1) space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Wildcard matching with glob expressions (? and *).
  • String matching with arbitrary length wildcards.

Algorithmic Decision Tree:

  • Wildcard matching with glob expressions (? and *).
  • String matching with arbitrary length wildcards.

Connected Patterns:

Regular Expression MatchingEdit DistanceInterleaving String

1. Top-Down Memoized Recursion

Intuition

Define solve(i, j) checking if s[i...] matches p[j...]. If j == p.length, return i == s.length. If p[j] == '*': return solve(i, j + 1) || (i < s.length && solve(i + 1, j)). If i < s.length && (p[j] == '?' || s[i] == p[j]): return solve(i + 1, j + 1). Memoize results in memo[i][j].

When to apply: Basic recursive baseline formulation.

Algorithm

  1. Initialize memo table of size (s.length + 1) x (p.length + 1) with -1.
  2. Helper dp(i, j):
  3. If j == p.length: return i == s.length.
  4. If memo[i][j] != -1: return memo[i][j].
  5. If p[j] == '*': result is dp(i, j + 1) || (i < s.length && dp(i + 1, j)).
  6. Else if i < s.length && (p[j] == '?' || s[i] == p[j]): result is dp(i + 1, j + 1).
  7. Else: result is false.
  8. Store and return memo[i][j].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6 int memo[2005][2005];
7 bool solve(int i, int j, const std::string& s, const std::string& p) {
8 if (j == p.size()) return i == s.size();
9 if (memo[i][j] != -1) return memo[i][j];
10
11 bool ans = false;
12 if (p[j] == '*') {
13 ans = solve(i, j + 1, s, p) || (i < s.size() && solve(i + 1, j, s, p));
14 } else if (i < s.size() && (p[j] == '?' || s[i] == p[j])) {
15 ans = solve(i + 1, j + 1, s, p);
16 }
17
18 return memo[i][j] = ans;
19 }
20public:
21 bool isMatch(std::string s, std::string p) {
22 for (int i = 0; i <= s.size(); ++i) {
23 for (int j = 0; j <= p.size(); ++j) {
24 memo[i][j] = -1;
25 }
26 }
27 return solve(0, 0, s, p);
28 }
29};
30
31int main() {
32 Solution sol;
33 std::cout << (sol.isMatch("adceb", "*a*b") ? "true" : "false") << std::endl; // true
34 std::cout << (sol.isMatch("cb", "?a") ? "true" : "false") << std::endl; // false
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(S * P) — There are S * P unique subproblems, each taking O(1) transitions.
  • Space complexity: O(S * P)

Why Brute Force Doesn't Scale:

Greedy pointer backtracking avoids full DP matrix allocation.

Strict O(1) auxiliary variables.

2. Bottom-Up 2D Dynamic Programming (Space-Optimized)

Intuition

Define dp[i][j] as matching status of s[0...i-1] and p[0...j-1]. Base cases: dp[0][0] = true. For j from 1 to P: dp[0][j] = dp[0][j - 1] && p[j - 1] == '*'. For each i from 1 to S and j from 1 to P: if p[j - 1] == '*': dp[i][j] = dp[i - 1][j] || dp[i][j - 1]. Else if p[j - 1] == '?' || p[j - 1] == s[i - 1]: dp[i][j] = dp[i - 1][j - 1]. We can reduce this to a single 1D row array.

When to apply: When non-recursive tabular dynamic programming is preferred.

Algorithm

  1. Initialize dp table of size (S + 1) x (P + 1) with false.
  2. dp[0][0] = true.
  3. For j from 1 to P: if p[j - 1] == '*': dp[0][j] = dp[0][j - 1].
  4. For i from 1 to S:
  5. For j from 1 to P:
  6. If p[j - 1] == '*': dp[i][j] = dp[i - 1][j] || dp[i][j - 1].
  7. Else if p[j - 1] == '?' || p[j - 1] == s[i - 1]: dp[i][j] = dp[i - 1][j - 1].
  8. Return dp[S][P].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 bool isMatch(std::string s, std::string p) {
8 int m = s.size(), n = p.size();
9 std::vector<bool> dp(n + 1, false);
10 dp[0] = true;
11
12 for (int j = 1; j <= n; ++j) {
13 if (p[j - 1] == '*') dp[j] = dp[j - 1];
14 }
15
16 for (int i = 1; i <= m; ++i) {
17 bool prevDiag = dp[0];
18 dp[0] = false;
19 for (int j = 1; j <= n; ++j) {
20 bool temp = dp[j];
21 if (p[j - 1] == '*') {
22 dp[j] = dp[j] || dp[j - 1];
23 } else if (p[j - 1] == '?' || p[j - 1] == s[i - 1]) {
24 dp[j] = prevDiag;
25 } else {
26 dp[j] = false;
27 }
28 prevDiag = temp;
29 }
30 }
31 return dp[n];
32 }
33};
34
35int main() {
36 Solution sol;
37 std::cout << (sol.isMatch("adceb", "*a*b") ? "true" : "false") << std::endl; // true
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(S * P) — Iterates through S * P grid; each cell computed in O(1) time.
  • Space complexity: O(P) 1D space

3. Greedy Two-Pointer Star Backtracking (Optimal O(1) Space)

Intuition

Maintain sIdx = 0, pIdx = 0, starIdx = -1, sMatch = 0. While sIdx < s.length: 1. If pIdx < p.length and characters match (p[pIdx] == '?' || p[pIdx] == s[sIdx]), advance sIdx++, pIdx++. 2. Else if pIdx < p.length && p[pIdx] == '*': record starIdx = pIdx, sMatch = sIdx, and advance pIdx++. 3. Else if starIdx != -1 (backtrack to last star): let the star match one more character: set pIdx = starIdx + 1, sMatch++, and sIdx = sMatch. 4. Else (mismatch with no previous star): return false. After s is consumed, advance pIdx skipping any trailing '*'. Return pIdx == p.length.

When to apply: The standard optimal solution achieving minimal memory and linear average time.

Algorithm

  1. Initialize sIdx = 0, pIdx = 0, starIdx = -1, sMatch = 0.
  2. While sIdx < s.length:
  3. If pIdx < p.length && (p[pIdx] == '?' || p[pIdx] == s[sIdx]): sIdx++; pIdx++.
  4. Else if pIdx < p.length && p[pIdx] == '*': starIdx = pIdx++; sMatch = sIdx.
  5. Else if starIdx != -1: pIdx = starIdx + 1; sMatch++; sIdx = sMatch.
  6. Else: return false.
  7. While pIdx < p.length && p[pIdx] == '*': pIdx++.
  8. Return pIdx == p.length.

Greedy Star-Track Backtracking Pointer Automation

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [a, c, d, c, b]
Current operationSTEP 1 OF 7
Observation: Compare s[0]='a' with p[0]='a'
Visual state
Values and pointers at this exact step
array
S
a
c
d
c
b
0
↑ sIdx=0 ('a') vs pIdx=0 ('a')
1
2
3
4
Variables at this step
sIdx
0
pIdx
0
charS
a
charP
a
match
true
starIdx
-1
Why this step matters

Observation: Compare s[0]='a' with p[0]='a'. Exact match.

Decision: Advance both pointers: sIdx = 1, pIdx = 1.

Invariant: Leading matching literals consumed directly.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 bool isMatch(std::string s, std::string p) {
7 int sIdx = 0, pIdx = 0;
8 int starIdx = -1, sMatch = 0;
9 int sLen = s.size(), pLen = p.size();
10
11 while (sIdx < sLen) {
12 // Case 1: Matching characters or __SF_TOKEN_A__
13 if (pIdx < pLen && (p[pIdx] == '?' || p[pIdx] == s[sIdx])) {
14 sIdx++;
15 pIdx++;
16 }
17 // Case 2: Star encountered
18 else if (pIdx < pLen && p[pIdx] == '*') {
19 starIdx = pIdx;
20 sMatch = sIdx;
21 pIdx++;
22 }
23 // Case 3: Mismatch but previous star exists -> backtrack
24 else if (starIdx != -1) {
25 pIdx = starIdx + 1;
26 sMatch++;
27 sIdx = sMatch;
28 }
29 // Case 4: Mismatch without any star
30 else {
31 return false;
32 }
33 }
34
35 // Skip trailing stars
36 while (pIdx < pLen && p[pIdx] == '*') {
37 pIdx++;
38 }
39
40 return pIdx == pLen;
41 }
42};
43
44int main() {
45 Solution sol;
46 std::cout << (sol.isMatch("adceb", "*a*b") ? "true" : "false") << std::endl; // true
47 std::cout << (sol.isMatch("aa", "a") ? "true" : "false") << std::endl; // false
48 std::cout << (sol.isMatch("aa", "*") ? "true" : "false") << std::endl; // true
49 return 0;
50}

Time & Space Complexity

  • Time complexity: O(S * P) worst case, O(S) average — Runs with zero dynamic memory allocation using 4 pointer variables.
  • Space complexity: O(1) strictly

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Top-Down Memoized RecursionO(S * P)O(S * P) recursion stack and memo tableIntuitive state transitions from base cases.High recursion overhead and large memo table.
2.Bottom-Up 2D Dynamic Programming (Space-Optimized)O(S * P)O(P) auxiliary arrayPredictable tabular evaluation without recursion limits.O(S * P) time complexity.
3.Greedy Two-Pointer Star Backtracking (Optimal)OptimalO(S * P) worst case, O(S) average caseO(1) strictlyStrictly constant auxiliary memory, fast single pass.Subtle backtracking pointers logic.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not checking trailing asterisks in pattern after exhausting string characters.

Pitfall 2:

Assuming earlier stars need to be backtracked (only the most recent star needs to absorb extra characters).

Crucial Edge Cases to Validate:

  • Empty s and empty p (s = '', p = ''): Returns true.
  • p consisting only of asterisks (s = abc, p = ***): Matches entire string and consumes trailing stars, returning true.
  • s is non-empty but p is empty (s = a, p = ''): Returns false.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Differentiate wildcard matching from regular expression matching clearly.
  2. Explain the greedy pointer backtrack algorithm with starIdx and sMatch.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is it sufficient to only backtrack to the MOST RECENT star character rather than all previous stars?

Back to DSA Sheet