# Wildcard Matching
**Difficulty:** HARD
[External](https://leetcode.com/problems/wildcard-matching)
Canonical: https://scaleengineer.com/dsa/problems/wildcard-matching
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Google](https://scaleengineer.com/companies/google), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Zoho](https://scaleengineer.com/companies/zoho), [Coupang](https://scaleengineer.com/companies/coupang), [Salesforce](https://scaleengineer.com/companies/salesforce), [Snap](https://scaleengineer.com/companies/snap), [Confluent](https://scaleengineer.com/companies/confluent), [X](https://scaleengineer.com/companies/x), [Twilio](https://scaleengineer.com/companies/twilio), [Two Sigma](https://scaleengineer.com/companies/two-sigma), [Instacart](https://scaleengineer.com/companies/instacart), [Coursera](https://scaleengineer.com/companies/coursera)
---
## Problem
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'.

**Constraints:**

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

# Approaches
## Recursive Approach
This approach directly translates the problem's definition into a recursive function. It explores all possible matching paths by making recursive calls. When a `*` is encountered in the pattern, the function branches into two recursive calls to explore both possibilities: the `*` matching an empty sequence, and the `*` matching one or more characters. This brute-force exploration of all paths leads to a very high time complexity.
**Time:** O(2^(m+n)) · **Space:** O(m + n)
**Pros:** Simple to understand and implement directly from the problem statement.; Clearly illustrates the recursive nature of the problem.
**Cons:** Extremely inefficient due to exponential time complexity.; Leads to a 'Time Limit Exceeded' (TLE) error for all but the smallest inputs.; Computes the same subproblems repeatedly.
### Explanation
The core idea is to define a helper function, say `solve(i, j)`, which returns `true` if the substring `s[i:]` matches the sub-pattern `p[j:]`. The logic proceeds by comparing characters at `s[i]` and `p[j]`.

- If `p[j]` is a normal character, it must match `s[i]`. If they match, we recurse on `solve(i+1, j+1)`.
- If `p[j]` is `?`, it matches any character, so we recurse on `solve(i+1, j+1)`.
- If `p[j]` is `*`, it creates a choice. The `*` can match nothing, so we check `solve(i, j+1)`. Or, it can match the character `s[i]` (and possibly more), so we check `solve(i+1, j)`. If either of these recursive calls returns `true`, then we have a match.

This method is simple to conceptualize but suffers from massive performance issues due to overlapping subproblems, where the function recalculates `solve(i, j)` for the same `i` and `j` multiple times.

```java
class Solution {
    public boolean isMatch(String s, String p) {
        return solve(s, p, 0, 0);
    }

    private boolean solve(String s, String p, int i, int j) {
        // If pattern is exhausted, string must also be exhausted for a match.
        if (j == p.length()) {
            return i == s.length();
        }

        char pChar = p.charAt(j);

        if (pChar == '*') {
            // Option 1: '*' matches empty sequence. Move to next pattern char.
            if (solve(s, p, i, j + 1)) {
                return true;
            }
            // Option 2: '*' matches current string char. Move to next string char.
            // This is only possible if string is not exhausted.
            if (i < s.length() && solve(s, p, i + 1, j)) {
                return true;
            }
        } else {
            // Check for a match of the current characters.
            boolean firstMatch = (i < s.length()) && (pChar == '?' || pChar == s.charAt(i));
            if (firstMatch && solve(s, p, i + 1, j + 1)) {
                return true;
            }
        }

        return false;
    }
}
```
### Algorithm
- Define a recursive function `isMatch(s_idx, p_idx)` that checks if `s` from index `s_idx` matches `p` from index `p_idx`.
- **Base Case 1:** If the pattern pointer `p_idx` reaches the end, the match is successful only if the string pointer `s_idx` has also reached the end.
- **Base Case 2:** If the string pointer `s_idx` reaches the end, the remainder of the pattern must consist solely of `*` characters to match an empty string.
- **Recursive Step for `*`:** If the current pattern character `p[p_idx]` is `*`, there are two possibilities:
  1. The `*` matches an empty sequence. We move to the next character in the pattern: `isMatch(s_idx, p_idx + 1)`.
  2. The `*` matches one or more characters. We consume a character from the string and stay at the same `*` in the pattern: `isMatch(s_idx + 1, p_idx)`. The result is true if either path succeeds.
- **Recursive Step for `?` or matching characters:** If `p[p_idx]` is `?` or equals `s[s_idx]`, we advance both pointers: `isMatch(s_idx + 1, p_idx + 1)`.
- **Mismatch:** If none of the above, it's a mismatch, return `false`.

## Dynamic Programming with Memoization (Top-Down)
To overcome the performance issues of the pure recursive approach, we can use memoization, a top-down dynamic programming technique. We store the results of each subproblem `(i, j)` in a cache or memoization table. Before computing the result for a subproblem, we first check if it's already in the cache. If it is, we return the cached value, avoiding redundant computation. This prunes the recursion tree significantly, reducing the time complexity from exponential to polynomial.
**Time:** O(m * n) · **Space:** O(m * n)
**Pros:** Drastically improves time complexity to polynomial time.; Guaranteed to pass within time limits for the given constraints.; Maintains the logical flow of the recursive solution, making it easier to transition to.
**Cons:** Requires O(m * n) space for the memoization table, which can be large.; Still has the overhead of recursion, which can be slower than an iterative DP solution.
### Explanation
We augment the recursive solution with a 2D array, `memo`, to store the outcomes of `solve(i, j)`. The state `(i, j)` represents the subproblem of matching `s.substring(i)` with `p.substring(j)`. We can use a `Boolean[][]` array, where `null` signifies an uncomputed state.

The logic of the recursive function remains identical, but with two key additions:
1.  **Check Memo:** At the beginning of the function, check `if (memo[i][j] != null)`. If it's not `null`, we've solved this subproblem before, so we return the stored result `memo[i][j]`.
2.  **Save to Memo:** After computing the result `ans` for the state `(i, j)`, we store it before returning: `memo[i][j] = ans`.

This ensures that each subproblem `(i, j)` is solved exactly once.

```java
class Solution {
    private Boolean[][] memo;
    private String s;
    private String p;

    public boolean isMatch(String s, String p) {
        this.s = s;
        this.p = p;
        this.memo = new Boolean[s.length() + 1][p.length() + 1];
        return solve(0, 0);
    }

    private boolean solve(int i, int j) {
        if (memo[i][j] != null) {
            return memo[i][j];
        }

        boolean ans;
        if (j == p.length()) {
            ans = (i == s.length());
        } else {
            char pChar = p.charAt(j);
            if (pChar == '*') {
                // '*' matches empty OR '*' matches one char from s
                ans = solve(i, j + 1) || (i < s.length() && solve(i + 1, j));
            } else {
                boolean firstMatch = (i < s.length()) && (pChar == '?' || pChar == s.charAt(i));
                ans = firstMatch && solve(i + 1, j + 1);
            }
        }
        
        return memo[i][j] = ans;
    }
}
```
### Algorithm
- The recursive structure is the same as the pure recursive approach.
- A 2D array, `memo[s.length() + 1][p.length() + 1]`, is used to store the results of subproblems.
- Initialize the `memo` table with a value indicating 'not computed' (e.g., `null`).
- In the recursive function `solve(i, j)`, first check if `memo[i][j]` has been computed. If yes, return the stored value.
- If not, compute the result using the same recursive logic as before.
- Before returning the computed result, store it in `memo[i][j]` for future use.

## Bottom-Up Dynamic Programming
This approach uses a bottom-up iterative method to solve the problem. It builds the solution from the smallest subproblems up to the final solution. A 2D table, `dp`, is used where `dp[i][j]` stores whether the prefix `s[0...i-1]` matches the prefix `p[0...j-1]`. The table is filled row by row, and each cell's value is computed based on the values of previously computed cells, representing smaller subproblems.
**Time:** O(m * n) · **Space:** O(m * n)
**Pros:** Efficient with a polynomial time complexity.; Avoids recursion overhead, which can lead to better performance in practice compared to memoization.; Can be space-optimized.
**Cons:** Requires O(m * n) space, which can be substantial for large strings.; Can be less intuitive to formulate than the top-down recursive approach for some.
### Explanation
We construct a DP table `dp` of size `(m+1) x (n+1)`, where `m` is the length of `s` and `n` is the length of `p`. The entry `dp[i][j]` holds the boolean result for `s.substring(0, i)` and `p.substring(0, j)`.

The table is filled based on the following rules:

1.  `dp[0][0] = true`: An empty string matches an empty pattern.
2.  `dp[0][j]` (first row): An empty string `s` can only be matched by a pattern `p` if the pattern consists of `*`s. So, `dp[0][j]` is true if `p[j-1]` is `*` and the pattern up to `j-1` also matched an empty string (`dp[0][j-1]`).
3.  For `i > 0` and `j > 0`:
    - If `p[j-1]` is a letter that matches `s[i-1]`, or if `p[j-1]` is `?`, then the current characters match. The result depends entirely on whether the prefixes before these characters matched: `dp[i][j] = dp[i-1][j-1]`.
    - If `p[j-1]` is `*`, it can either be ignored (matching an empty sequence), in which case the result is `dp[i][j-1]`, or it can match `s[i-1]`, in which case the result depends on `dp[i-1][j]`. Thus, `dp[i][j] = dp[i][j-1] || dp[i-1][j]`.

The final answer is located at `dp[m][n]`.

```java
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];

        dp[0][0] = true;

        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }

        return dp[m][n];
    }
}
```
### Algorithm
- Create a 2D boolean array `dp` of size `(s.length + 1) x (p.length + 1)`.
- `dp[i][j]` will be `true` if the first `i` characters of `s` match the first `j` characters of `p`.
- **Initialization:**
  - `dp[0][0] = true` (empty string matches empty pattern).
  - For the first row (`i=0`), `dp[0][j]` is `true` if `p[j-1]` is `*` and `dp[0][j-1]` was `true`. This handles patterns like `*`, `a*`, `**` matching an empty string.
- **Transitions:** Iterate from `i = 1` to `s.length` and `j = 1` to `p.length`:
  - If `p[j-1]` is `?` or `p[j-1] == s[i-1]`, the match depends on the previous substrings: `dp[i][j] = dp[i-1][j-1]`.
  - If `p[j-1]` is `*`, it can either match an empty sequence (look at `dp[i][j-1]`) or match the current character `s[i-1]` (look at `dp[i-1][j]`). So, `dp[i][j] = dp[i][j-1] || dp[i-1][j]`.
  - Otherwise, `dp[i][j] = false`.
- **Result:** The final answer is `dp[s.length][p.length]`.

## Greedy Approach with Backtracking
This is a highly efficient iterative approach that uses a greedy strategy with backtracking capabilities. It traverses the string and pattern using pointers. It greedily matches characters one by one. When it encounters a `*`, it makes a greedy choice (assuming `*` matches an empty sequence) but saves the `*`'s position as a backtrack point. If a future mismatch occurs, it can return to this saved `*` and have it match more characters from the string. This avoids the large space requirement of DP while often being faster in practice.
**Time:** O(m * n) · **Space:** O(1)
**Pros:** Extremely space-efficient, using only O(1) extra space.; Very fast on average, often outperforming DP solutions in practice.; It is an iterative solution, so it does not risk a stack overflow.
**Cons:** The logic is more complex and less straightforward to understand than DP approaches.; The worst-case time complexity is still O(m * n), though it's rare in practice.
### Explanation
This method cleverly uses a constant amount of extra space by keeping track of the last seen `*` character in the pattern. This `*` serves as a fallback point.

We iterate through the string `s` with a pointer `sPtr`. 
- If the characters at `sPtr` and `pPtr` match (or `p[pPtr]` is `?`), we advance both pointers.
- If `p[pPtr]` is `*`, we record its position (`starIdx`) and the current string position (`sMatchIdx`). We then advance `pPtr` but not `sPtr`, greedily assuming the `*` matches an empty string.
- If we encounter a mismatch and `p[pPtr]` is not `*`, we check if we have a `starIdx` to fall back on. If we do, it means our previous greedy assumption about the `*` was wrong. We must backtrack: we reset `pPtr` to the position after the star (`starIdx + 1`) and set `sPtr` to `sMatchIdx + 1`. We also increment `sMatchIdx` itself, so the next time we backtrack to this same star, it will match an even longer sequence. 
- If we mismatch and have no `starIdx` to backtrack to, the match fails.

After the string `s` is fully traversed, any remaining characters in `p` must be `*` for a valid match.

```java
class Solution {
    public boolean isMatch(String s, String p) {
        int sPtr = 0, pPtr = 0;
        int starIdx = -1, sMatchIdx = 0;

        while (sPtr < s.length()) {
            // Case 1: Characters match or pattern has '?'
            if (pPtr < p.length() && (p.charAt(pPtr) == '?' || p.charAt(pPtr) == s.charAt(sPtr))) {
                sPtr++;
                pPtr++;
            } 
            // Case 2: Pattern has '*'
            else if (pPtr < p.length() && p.charAt(pPtr) == '*') {
                starIdx = pPtr;
                sMatchIdx = sPtr;
                pPtr++;
            } 
            // Case 3: Mismatch, but we can backtrack to a '*'
            else if (starIdx != -1) {
                pPtr = starIdx + 1;
                sMatchIdx++;
                sPtr = sMatchIdx;
            } 
            // Case 4: Mismatch and no '*' to backtrack to
            else {
                return false;
            }
        }

        // Check for remaining characters in pattern (must be '*')
        while (pPtr < p.length() && p.charAt(pPtr) == '*') {
            pPtr++;
        }

        return pPtr == p.length();
    }
}
```
### Algorithm
- Use two pointers for the string (`sPtr`) and pattern (`pPtr`).
- Use two additional variables to handle `*`: `starIdx` to store the position of the last `*` in the pattern, and `sMatchIdx` to store the position in the string that was matched up to that `*`.
- **Iterate through the string `s` with `sPtr`:**
  1. If `p[pPtr]` matches `s[sPtr]` (or is `?`), advance both `sPtr` and `pPtr`.
  2. If `p[pPtr]` is `*`, save its position in `starIdx` and the current `sPtr` in `sMatchIdx`. Then, advance only `pPtr`, effectively treating `*` as matching an empty sequence for now.
  3. If a mismatch occurs and a `*` has been seen before (`starIdx != -1`), backtrack. Move `pPtr` to `starIdx + 1`, and advance `sMatchIdx`. Then, set `sPtr = sMatchIdx`. This makes the `*` consume one more character from the string.
  4. If a mismatch occurs and no `*` has been seen, a match is impossible. Return `false`.
- **After the loop:** Once `sPtr` has traversed the entire string, any remaining characters in the pattern must be `*`s. Advance `pPtr` past any trailing `*`s.
- **Result:** The match is successful if `pPtr` has reached the end of the pattern.

# Solutions
### CSharp

```csharp
using System.Linq ; public class Solution { public bool IsMatch ( string s , string p ) { if ( p . Count ( ch => ch != '*' ) > s . Length ) { return false ; } bool [,] f = new bool [ s . Length + 1 , p . Length + 1 ]; bool [] d = new bool [ s . Length + 1 ]; // d[i] means f[0, j] || f[1, j] || ... || f[i, j] for ( var j = 0 ; j <= p . Length ; ++ j ) { d [ 0 ] = j == 0 ? true : d [ 0 ] && p [ j - 1 ] == '*' ; for ( var i = 0 ; i <= s . Length ; ++ i ) { if ( j == 0 ) { f [ i , j ] = i == 0 ; continue ; } if ( p [ j - 1 ] == '*' ) { if ( i > 0 ) { d [ i ] = f [ i , j - 1 ] || d [ i - 1 ]; } f [ i , j ] = d [ i ]; } else if ( p [ j - 1 ] == '?' ) { f [ i , j ] = i > 0 && f [ i - 1 , j - 1 ]; } else { f [ i , j ] = i > 0 && f [ i - 1 , j - 1 ] && s [ i - 1 ] == p [ j - 1 ]; } } } return f [ s . Length , p . Length ]; } }
```

### Java

```java
class Solution { public boolean isMatch ( String s , String p ) { int m = s . length (), n = p . length (); boolean [][] dp = new boolean [ m + 1 ][ n + 1 ]; dp [ 0 ][ 0 ] = true ; for ( int j = 1 ; j <= n ; ++ j ) { if ( p . charAt ( j - 1 ) == '*' ) { dp [ 0 ][ j ] = dp [ 0 ][ j - 1 ]; } } for ( int i = 1 ; i <= m ; ++ i ) { for ( int j = 1 ; j <= n ; ++ j ) { if ( s . charAt ( i - 1 ) == p . charAt ( j - 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 [ m ][ n ]; } }
```

### CPP

```cpp
class Solution { public: bool isMatch ( string s , string p ) { int m = s . size (), n = p . size (); vector < vector < bool >> dp ( m + 1 , vector < bool > ( n + 1 )); dp [ 0 ][ 0 ] = true ; for ( int j = 1 ; j <= n ; ++ j ) { if ( p [ j - 1 ] == '*' ) { dp [ 0 ][ j ] = dp [ 0 ][ j - 1 ]; } } for ( int i = 1 ; i <= m ; ++ i ) { for ( int j = 1 ; j <= n ; ++ j ) { if ( s [ i - 1 ] == p [ j - 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 [ m ][ n ]; } };
```

### Python

```python
class Solution : def isMatch ( self , s : str , p : str ) -> bool : m , n = len ( s ), len ( p ) dp = [[ False ] * ( n + 1 ) for _ in range ( m + 1 )] dp [ 0 ][ 0 ] = True # if p starting with "*", then all true for dp[0][i] # or else, all false for dp[0][i] for j in range ( 1 , n + 1 ): if p [ j - 1 ] == '*' : dp [ 0 ][ j ] = dp [ 0 ][ j - 1 ] for i in range ( 1 , m + 1 ): for j in range ( 1 , n + 1 ): if s [ i - 1 ] == p [ j - 1 ] or p [ j - 1 ] == '?' : dp [ i ][ j ] = dp [ i - 1 ][ j - 1 ] # dp[i - 1][j], where j is always '*', all the way back to i-1==0 elif p [ j - 1 ] == '*' : dp [ i ][ j ] = dp [ i - 1 ][ j ] or dp [ i ][ j - 1 ] return dp [ m ][ n ]
```