> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/dynamic-programming/dp-on-strings/wildcard-matching.md).

# Wildcard Matching

## 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:**

<pre><code><strong>Input: s = "aa", p = "a"
</strong><strong>Output: false
</strong><strong>Explanation: "a" does not match the entire string "aa".
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "aa", p = "*"
</strong><strong>Output: true
</strong><strong>Explanation: '*' matches any sequence.
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: s = "cb", p = "?a"
</strong><strong>Output: false
</strong><strong>Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
</strong></code></pre>

&#x20;

**Constraints:**

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

## Intuition

```
For matching a character and ? 
We can match directly, reduce both by 1

But for * we match multiple using for loop 
```

### Links

<https://leetcode.com/problems/wildcard-matching/description/>

### Video Links

<https://www.youtube.com/watch?v=ZmlQ3vgAOMo&ab_channel=takeUforward>

### Approach 1:

```
Memoization
```

{% code title="C++" lineNumbers="true" %}

````cpp
class Solution {
public:
    bool find_ans(string &s, string &t, int i, int j, vector<vector<int>> &dp){
        //Entire string matched
        if(i<0 and j<0)
            return true;

        if(i<0 and j>=0){
            /* 
            This entire block is added to take care of this type of testcase
            when first string gets exhausted and second has leading *

            abba
            *****abba

            To match all the leading * with empty 
            */
            int flag = 1;

            for(int start=j; start>=0; start--)
                if(t[start] != '*')
                    flag=0;

            if(flag)
                return true;

            return false;
        }

        if(i>=0 and j<0)
            return false;

        if(dp[i][j] != -1)
            return dp[i][j];
            
        // Match single string
        if(s[i] == t[j] or t[j] == '?'){
            if( find_ans(s, t, i-1, j-1, dp) )
                return dp[i][j] = true;
        }
        // Match ith to 0 index for a single *
        else if(t[j] == '*'){
            for(int start=0; start<=i+1; start++) {
                if( find_ans(s, t, i-start, j-1, dp) )
                    return dp[i][j] = true;
            }
        }

        return dp[i][j] = false;
    }

    bool isMatch(string s, string t) {
        int m = s.size();
        int n = t.size();
        vector<vector<int>> dp (m, vector<int> (n,-1));

        return find_ans(s, t, m-1, n-1, dp);
    }
};
```
````

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems