Course4all
Join us on telegram
Home/dsa/Backtracking/Wildcard Matching

Wildcard Matching

Master this topic with zero to advance depth.

Wildcard Matching

Matching Rules

  • '?' matches any single character.
  • '*' matches any sequence of characters (including empty sequence).

The Greedy '*' Logic

Unlike Regular Expression matching where a* depends on 'a', the Wildcard * is independent. It can match anything. This makes it a great candidate for greedy search or dynamic programming.

Implement wildcard pattern matching with support for '?' and '*'. Includes visual matching trace.

Hard

Examples

Input: s = "aa", p = "*"
Output: true
Input: s = "cb", p = "?a"
Output: false
Approach 1

Level I: Recursive Backtracking (Naive)

Intuition

Traverse both strings. If we hit '?', match one. If we hit '*', try matching zero or more characters.

Standard recursion with branching on '*'. This is O(2N)O(2^N) in the worst case (e.g., s="aaaaa", p="*a*a*a").

⏱ O(2^N)💾 O(N)

Detailed Dry Run

s="aa", p="*" | Step | s | p | Action | | :--- | :--- | :--- | :--- | | 1 | "aa" | "*" | '*' detected, branch | | 2.1 | "aa" | "" | FAIL (skip *) | | 2.2 | "a" | "*" | RECURSE (consume 'a') | | 3.1 | "a" | "" | FAIL (skip *) | | 3.2 | "" | "*" | SUCCESS (consume 'a', match empty) |
java
class Solution {
    public boolean isMatch(String s, String p) {
        return backtrack(s, p, 0, 0);
    }
    private boolean backtrack(String s, String p, int i, int j) {
        if (j == p.length()) return i == s.length();
        if (p.charAt(j) == '*') {
            return backtrack(s, p, i, j + 1) || (i < s.length() && backtrack(s, p, i + 1, j));
        }
        if (i < s.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
            return backtrack(s, p, i + 1, j + 1);
        }
        return false;
    }
}
Approach 2

Level II: Top-Down Memoization

Intuition

Overlap in recursive branches for '*' leads to redundant work.

Store (i, j) match results to achieve O(SimesP)O(S imes P) complexity.

⏱ O(S * P)💾 O(S * P)

Detailed Dry Run

For s="abc", p="*c": memo[0][0] calls memo[0][1] and memo[1][0]. memo[1][0] calls memo[1][1] and memo[2][0]. Redundant paths like (*, c) matching 'bc' are cached.
java
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        Boolean[][] memo = new Boolean[m + 1][n + 1];
        return dp(0, 0, s, p, memo);
    }
    private boolean dp(int i, int j, String s, String p, Boolean[][] memo) {
        if (j == p.length()) return i == s.length();
        if (memo[i][j] != null) return memo[i][j];
        
        boolean res;
        if (p.charAt(j) == '*') {
            res = dp(i, j+1, s, p, memo) || (i < s.length() && dp(i+1, j, s, p, memo));
        } else if (i < s.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
            res = dp(i+1, j+1, s, p, memo);
        } else {
            res = false;
        }
        return memo[i][j] = res;
    }
}
Approach 3

Level III: Optimized Greedy Path (Pointers)

Intuition

Instead of a full DP table, we can track the last '*' position and backtrack only as much as needed.

When we hit '', record the current s and p indices. If we hit a mismatch later, reset p to right after '', and s to one char after the previous recorded s index.

⏱ O(S * P) worst case, O(S) average.💾 O(1) extra.

Detailed Dry Run

s="adceb", p="*a*b" 1. p[0]='*', star_idx=0, s_tmp=0. p moves to 1. 2. s[0]='a', p[1]='a'. Match! i=1, j=2. 3. p[2]='*', star_idx=2, s_tmp=1. p moves to 3. 4. s[1]='d', p[3]='b'. Mismatch! Backtrack to star_idx=2, s_tmp=2. 5. Keep trying until s[4]='b', p[3]='b'. MATCH!
java
class Solution {
    public boolean isMatch(String s, String p) {
        int i = 0, j = 0, starIdx = -1, sTmp = -1;
        while (i < s.length()) {
            if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
                i++; j++;
            } else if (j < p.length() && p.charAt(j) == '*') {
                starIdx = j;
                sTmp = i;
                j++;
            } else if (starIdx != -1) {
                j = starIdx + 1;
                i = ++sTmp;
            } else {
                return false;
            }
        }
        while (j < p.length() && p.charAt(j) == '*') j++;
        return j == p.length();
    }
}
← Previous QuestionRegular Expression Matching
Next Question →Partition to K Equal Sum Subsets