Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Wildcard Matching

HARDProblemSolveExternal Links

Description

Given an input string s and a pattern p, implement wildcard pattern matching with support for two special characters:

  • '?' — Matches any single character.
  • '*' — Matches any sequence of characters, including an empty sequence (zero characters).

The matching must cover the entire input string from start to finish — partial matches do not count.

Your task is to determine whether the pattern p fully matches the string s.

Examples

Example 1

Input: s = "aa", p = "a"

Output: false

Explanation: The pattern "a" consists of a single character 'a'. It can only match a string of length 1. Since s has length 2, the pattern cannot cover the entire string. There is no wildcard to absorb the extra character.

Example 2

Input: s = "aa", p = "*"

Output: true

Explanation: The '*' wildcard matches any sequence of characters, including a sequence of length 2. So '*' absorbs the entire string "aa", and the match succeeds.

Example 3

Input: s = "cb", p = "?a"

Output: false

Explanation: The '?' in the pattern matches the first character 'c' in the string (since '?' matches any single character). However, the second character in the pattern is 'a', which does not match 'b' in the string. Since one character fails to match, the overall result is false.

Example 4

Input: s = "adceb", p = "ab"

Output: true

Explanation: The first '*' matches an empty sequence (zero characters). Then 'a' matches 'a'. The second '*' matches the substring "dce". Finally 'b' matches 'b'. Every character in the string is accounted for, so the result is true.

Constraints

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

Editorial

Brute Force

Intuition

The most natural way to approach wildcard matching is to think recursively. We compare the string and pattern character by character from the beginning.

  • If the current pattern character is a normal letter or '?', the decision is simple: the current string character must match (for a letter) or can be anything (for '?'). Then we recurse on the remaining portions of both strings.
  • The tricky part is '*'. Since '*' can match zero or more characters, we face a branching decision: does this '*' consume zero characters from the string, or one character, or two, or three, and so on? We try each possibility recursively.

This is like standing at a fork in a road where one sign says "take nothing" and another says "take one more step." At every '*', we explore both paths, which creates an exponential explosion of possibilities.

The key insight is that this brute-force recursion is correct but extremely slow because it re-explores many identical subproblems over and over.

Step-by-Step Explanation

Let's trace through with s = "adceb", p = "ab":

Step 1: Call match(s=0, p=0). Pattern char is '*'. We branch:

  • Option A: '*' matches empty → recurse match(s=0, p=1)
  • Option B: '*' matches s[0]='a' → recurse match(s=1, p=0)

Step 2: Follow Option A: match(s=0, p=1). Pattern char is 'a', string char is 'a'. They match! Recurse match(s=1, p=2).

Step 3: match(s=1, p=2). Pattern char is '*'. Branch again:

  • Option A: '*' matches empty → recurse match(s=1, p=3)
  • Option B: '*' matches s[1]='d' → recurse match(s=2, p=2)

Step 4: Follow Option A: match(s=1, p=3). Pattern char is 'b', string char is 'd'. Mismatch! Return false.

Step 5: Backtrack to Step 3, try Option B: match(s=2, p=2). Pattern char is '*'. Branch:

  • Option A: match(s=2, p=3) → pattern='b', string='c' → mismatch, false
  • Option B: match(s=3, p=2) → continue exploring...

Step 6: match(s=3, p=2). Pattern char is '*'. Branch:

  • Option A: match(s=3, p=3) → pattern='b', string='e' → mismatch, false
  • Option B: match(s=4, p=2) → continue exploring...

Step 7: match(s=4, p=2). Pattern char is '*'. Branch:

  • Option A: match(s=4, p=3) → pattern='b', string='b' → MATCH! Recurse match(s=5, p=4).
  • Option B: match(s=5, p=2) → s is empty but pattern has more → explore...

Step 8: match(s=5, p=4). Both s and p exhausted. Return true!

Result: true. But notice the extensive branching — many dead-end paths explored.

Wildcard Matching — Recursive Branching at '*' — Watch how each '*' in the pattern creates two branches: skip the star or consume one more character from the string. Many branches lead to dead ends before we find the successful path.

Algorithm

  1. Define a recursive function match(i, j) where i is the current index in string s and j is the current index in pattern p.
  2. Base cases:
    • If both i and j have reached the end of their respective strings, return true (complete match).
    • If j has reached the end of the pattern but i hasn't, return false (pattern too short).
    • If i has reached the end of s but j hasn't, return true only if all remaining pattern characters are '*'.
  3. Recursive cases:
    • If p[j] is a letter or '?': check that s[i] matches, then recurse on match(i+1, j+1).
    • If p[j] is '*': try both options — match(i, j+1) (star matches empty) OR match(i+1, j) (star consumes one character).
  4. Return the result.

Code

class Solution {
public:
    bool isMatch(string s, string p) {
        return helper(s, p, 0, 0);
    }
    
    bool helper(string& s, string& p, int i, int j) {
        // Both exhausted
        if (i == s.size() && j == p.size()) return true;
        // Pattern exhausted but string remains
        if (j == p.size()) return false;
        // String exhausted — remaining pattern must be all '*'
        if (i == s.size()) {
            while (j < p.size()) {
                if (p[j] != '*') return false;
                j++;
            }
            return true;
        }
        
        if (p[j] == '?' || p[j] == s[i]) {
            return helper(s, p, i + 1, j + 1);
        } else if (p[j] == '*') {
            // Star matches empty OR star consumes one char
            return helper(s, p, i, j + 1) || helper(s, p, i + 1, j);
        }
        return false;
    }
};
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        def helper(i: int, j: int) -> bool:
            # Both exhausted
            if i == len(s) and j == len(p):
                return True
            # Pattern exhausted but string remains
            if j == len(p):
                return False
            # String exhausted — remaining pattern must be all '*'
            if i == len(s):
                return all(p[k] == '*' for k in range(j, len(p)))
            
            if p[j] == '?' or p[j] == s[i]:
                return helper(i + 1, j + 1)
            elif p[j] == '*':
                # Star matches empty OR star consumes one char
                return helper(i, j + 1) or helper(i + 1, j)
            return False
        
        return helper(0, 0)
class Solution {
    public boolean isMatch(String s, String p) {
        return helper(s, p, 0, 0);
    }
    
    private boolean helper(String s, String p, int i, int j) {
        // Both exhausted
        if (i == s.length() && j == p.length()) return true;
        // Pattern exhausted but string remains
        if (j == p.length()) return false;
        // String exhausted — remaining pattern must be all '*'
        if (i == s.length()) {
            while (j < p.length()) {
                if (p.charAt(j) != '*') return false;
                j++;
            }
            return true;
        }
        
        if (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i)) {
            return helper(s, p, i + 1, j + 1);
        } else if (p.charAt(j) == '*') {
            return helper(s, p, i, j + 1) || helper(s, p, i + 1, j);
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(2^(n+m))

In the worst case, every '*' in the pattern creates two recursive branches. If the pattern is all '*' characters, we branch at every step, leading to an exponential number of recursive calls. For a string of length n and pattern of length m, the recursion tree can grow as large as 2^(n+m).

Space Complexity: O(n + m)

The recursion depth is bounded by n + m (we either advance in the string or in the pattern at each call), so the call stack uses O(n + m) space.

Why This Approach Is Not Efficient

The brute force recursion has exponential time complexity O(2^(n+m)). With constraints allowing n and m up to 2000, this means up to 2^4000 operations in the worst case — astronomically beyond any time limit.

The root cause of the inefficiency is overlapping subproblems. The same pair of indices (i, j) can be reached through many different recursive paths. For example, match(3, 2) might be called from match(2, 2) (star consumes one character) and also from match(3, 1) (different branch). Each time, the entire subtree below that call is recomputed from scratch.

Key insight: if we store the result of each unique (i, j) pair the first time we compute it and reuse it on subsequent encounters, we eliminate all redundant work. This is the principle of memoization, and it reduces the problem to at most n × m unique subproblems.

Better Approach - Dynamic Programming (Tabulation)

Intuition

Instead of recursing top-down with memoization, we can fill a 2D table bottom-up. Define dp[i][j] as: does the first i characters of the string match the first j characters of the pattern?

The table has dimensions (n+1) × (m+1) where n = len(s) and m = len(p). The extra row and column handle the empty-string base cases.

Base cases:

  • dp[0][0] = true — empty string matches empty pattern.
  • dp[0][j] = true only if the first j characters of the pattern are all '*' (since each '*' can match empty).
  • dp[i][0] = false for i > 0 — a non-empty string cannot match an empty pattern.

Transitions:

  • If p[j-1] is a letter or '?': dp[i][j] = dp[i-1][j-1] (both advance by one character).
  • If p[j-1] is '*': dp[i][j] = dp[i-1][j] (star consumes s[i]) OR dp[i][j-1] (star matches empty).

Think of the table as a grid where you can move diagonally (character match), leftward (star matches empty), or downward (star consumes a character). If you can find a path from dp[0][0] to dp[n][m] through only true cells, the answer is true.

Step-by-Step Explanation

Let's trace with s = "adceb", p = "ab" (n=5, m=4):

We build a 6×5 DP table (rows 0..5 for s, columns 0..4 for p).

Step 1: Initialize dp[0][0] = true. Empty string matches empty pattern.

Step 2: Fill row 0 (empty string vs pattern prefix). dp[0][1]: p[0]='' can match empty → dp[0][1] = dp[0][0] = true. dp[0][2]: p[1]='a' is not '' → dp[0][2] = false. dp[0][3] and dp[0][4] also false.

Step 3: Fill dp[1][1]: s='a', p='*'. Star can match 'a' → dp[1][1] = dp[0][1] (star consumes 'a') = true.

Step 4: Fill dp[1][2]: s='a', p='*a'. p[1]='a' matches s[0]='a' → dp[1][2] = dp[0][1] = true.

Step 5: Fill dp[1][3]: s='a', p='a'. p[2]='*' → dp[1][3] = dp[0][3] OR dp[1][2] = false OR true = true.

Step 6: Fill dp[1][4]: s='a', p='ab'. p[3]='b' ≠ s[0]='a' → dp[1][4] = false.

Step 7: Continue filling rows 2-5. At dp[2][3] (s='ad', p='a'), the second '' absorbs 'd' via dp[1][3]=true. Similarly dp[3][3], dp[4][3] are true as '' absorbs more.

Step 8: dp[5][4] (s='adceb', p='ab'): p[3]='b', s[4]='b', match → dp[5][4] = dp[4][3] = true.

Result: dp[5][4] = true.

Wildcard Matching — DP Table Construction — Watch as we fill the DP table cell by cell. Each cell dp[i][j] tells us whether the first i characters of s match the first j characters of p.

Algorithm

  1. Create a 2D boolean table dp of size (n+1) × (m+1), initialized to false.
  2. Set dp[0][0] = true.
  3. Fill row 0: for each j from 1 to m, if p[j-1] == '*', set dp[0][j] = dp[0][j-1].
  4. For each row i from 1 to n:
    • For each column j from 1 to m:
      • If p[j-1] == s[i-1] or p[j-1] == '?': set dp[i][j] = dp[i-1][j-1]
      • Else if p[j-1] == '*': set dp[i][j] = dp[i-1][j] || dp[i][j-1]
      • Else: dp[i][j] remains false (character mismatch)
  5. Return dp[n][m].

Code

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
        dp[0][0] = true;
        
        // Fill row 0: empty string vs pattern prefix
        for (int j = 1; j <= m; j++) {
            if (p[j - 1] == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p[j - 1] == s[i - 1] || p[j - 1] == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p[j - 1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }
            }
        }
        
        return dp[n][m];
    }
};
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n, m = len(s), len(p)
        dp = [[False] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = True
        
        # Fill row 0: empty string vs pattern prefix
        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] == s[i - 1] or p[j - 1] == '?':
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
        
        return dp[n][m]
class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length();
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        
        // Fill row 0: empty string vs pattern prefix
        for (int j = 1; j <= m; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }
            }
        }
        
        return dp[n][m];
    }
}

Complexity Analysis

Time Complexity: O(n × m)

We fill a table with (n+1) rows and (m+1) columns. Each cell takes O(1) to compute since we only look at neighboring cells. Total: (n+1) × (m+1) ≈ O(n × m). For n = m = 2000, this is 4 × 10^6 operations — well within time limits.

Space Complexity: O(n × m)

The 2D DP table requires (n+1) × (m+1) boolean entries. For n = m = 2000, this is about 4 million booleans (~4 MB), which is acceptable.

Why This Approach Is Not Efficient

The 2D DP approach works correctly in O(n × m) time, which is sufficient for the given constraints. However, it uses O(n × m) space for the full DP table.

When we examine the DP recurrence closely, each cell dp[i][j] depends only on:

  • dp[i-1][j-1] (diagonal — used when characters match)
  • dp[i-1][j] (cell above — used when '*' consumes a character)
  • dp[i][j-1] (cell to the left — used when '*' matches empty)

This means we only ever need the current row and the previous row — the rest of the table is dead data. We can reduce space from O(n × m) to O(m) by maintaining just two 1D arrays.

But we can do even better: there exists a two-pointer approach with O(1) space that avoids the DP table entirely. By carefully managing backtracking positions when we encounter '*', we can solve the problem in linear-like time with constant extra memory.

Optimal Approach - Two Pointer with Star Backtracking

Intuition

The key insight for the optimal approach is that we do not need to explore all possible ways '*' can match. Instead, we use a greedy strategy with backtracking.

We maintain two pointers — one for the string (i) and one for the pattern (j). We process characters one by one:

  1. Character match or '?': Both pointers advance together. Simple.
  2. '*' encountered: We record the position of this star in the pattern (starIdx = j) and the current string position (matchIdx = i). Then we advance j past the star, initially assuming it matches zero characters.
  3. Mismatch with no current star: If characters don't match and there's no star to fall back on, the answer is false.
  4. Mismatch with a previous star: We backtrack to the last star. We assume the star matches one more character than before: advance matchIdx by one, reset i to the new matchIdx, and reset j to just after the star.

The trick is that we only need to remember the most recent '*' position. When we encounter a new '*', it supersedes the old one because it can absorb everything between the two stars.

Think of it like navigating a maze: when you hit a dead end, you go back to the last fork (the last '*') and try a slightly different path (let the star consume one more character).

Step-by-Step Explanation

Let's trace with s = "adceb", p = "ab":

Step 1: Initialize i=0, j=0, starIdx=-1, matchIdx=0.

Step 2: p[0]='*'. Record starIdx=0, matchIdx=0. Advance j to 1. (Star initially matches zero characters.)

Step 3: p[1]='a', s[0]='a'. Characters match! Advance both: i=1, j=2.

Step 4: p[2]='*'. Record starIdx=2, matchIdx=1. Advance j to 3. (Second star initially matches zero characters.)

Step 5: p[3]='b', s[1]='d'. Mismatch! But we have a star at starIdx=2. Backtrack: matchIdx becomes 2, i=2, j=3. (Star now matches s[1]='d'.)

Step 6: p[3]='b', s[2]='c'. Mismatch again. Backtrack: matchIdx becomes 3, i=3, j=3. (Star now matches 'dc'.)

Step 7: p[3]='b', s[3]='e'. Mismatch again. Backtrack: matchIdx becomes 4, i=4, j=3. (Star now matches 'dce'.)

Step 8: p[3]='b', s[4]='b'. Match! Advance both: i=5, j=4.

Step 9: i=5 (past end of s), j=4 (past end of p). Both exhausted. Return true!

Wildcard Matching — Two-Pointer with Star Backtracking — Watch how two pointers walk through the string and pattern. When a mismatch occurs, we backtrack to the last '*' and let it consume one more character, then retry.

Algorithm

  1. Initialize pointers i = 0 (string), j = 0 (pattern), starIdx = -1 (last star position), matchIdx = 0 (string position when last star was recorded).
  2. While i < len(s):
    a. If j < len(p) and (p[j] == s[i] or p[j] == '?'): advance both i and j.
    b. Else if j < len(p) and p[j] == '*': record starIdx = j, matchIdx = i, advance j.
    c. Else if starIdx != -1: backtrack — j = starIdx + 1, matchIdx++, i = matchIdx.
    d. Else: return false (no match possible).
  3. After the loop, skip any remaining '*' characters in the pattern.
  4. Return j == len(p).

Code

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        int i = 0, j = 0;
        int starIdx = -1, matchIdx = 0;
        
        while (i < n) {
            // Characters match or '?' matches any
            if (j < m && (p[j] == s[i] || p[j] == '?')) {
                i++;
                j++;
            }
            // Star: record position, assume matches empty
            else if (j < m && p[j] == '*') {
                starIdx = j;
                matchIdx = i;
                j++;
            }
            // Mismatch but we have a star to backtrack to
            else if (starIdx != -1) {
                j = starIdx + 1;
                matchIdx++;
                i = matchIdx;
            }
            // No match possible
            else {
                return false;
            }
        }
        
        // Skip remaining '*' in pattern
        while (j < m && p[j] == '*') {
            j++;
        }
        
        return j == m;
    }
};
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n, m = len(s), len(p)
        i, j = 0, 0
        star_idx, match_idx = -1, 0
        
        while i < n:
            # Characters match or '?' matches any
            if j < m and (p[j] == s[i] or p[j] == '?'):
                i += 1
                j += 1
            # Star: record position, assume matches empty
            elif j < m and p[j] == '*':
                star_idx = j
                match_idx = i
                j += 1
            # Mismatch but we have a star to backtrack to
            elif star_idx != -1:
                j = star_idx + 1
                match_idx += 1
                i = match_idx
            # No match possible
            else:
                return False
        
        # Skip remaining '*' in pattern
        while j < m and p[j] == '*':
            j += 1
        
        return j == m
class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length();
        int i = 0, j = 0;
        int starIdx = -1, matchIdx = 0;
        
        while (i < n) {
            // Characters match or '?' matches any
            if (j < m && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '?')) {
                i++;
                j++;
            }
            // Star: record position, assume matches empty
            else if (j < m && p.charAt(j) == '*') {
                starIdx = j;
                matchIdx = i;
                j++;
            }
            // Mismatch but we have a star to backtrack to
            else if (starIdx != -1) {
                j = starIdx + 1;
                matchIdx++;
                i = matchIdx;
            }
            // No match possible
            else {
                return false;
            }
        }
        
        // Skip remaining '*' in pattern
        while (j < m && p.charAt(j) == '*') {
            j++;
        }
        
        return j == m;
    }
}

Complexity Analysis

Time Complexity: O(n × m) in the worst case

In the worst case (e.g., s = "aaaa...a", p = "aa*a...a"), each backtrack can reset the string pointer, potentially causing us to re-scan portions of the string. The worst case occurs when we have many '*' characters interleaved with matching characters, leading to roughly O(n × m) work. In practice for typical inputs, performance is much closer to O(n + m).

Space Complexity: O(1)

We use only four integer variables (i, j, starIdx, matchIdx) regardless of input size. No DP table, no recursion stack, no additional data structures. This is the key advantage over the DP approach — constant extra memory.