> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/wildcard-matching.md).

# 44. Wildcard Matching

### Description

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

'?' Matches any single character.

'\*' Matches any sequence of characters (including the empty sequence).

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

### Constraints

* `s` could be empty or contains only lowercase letters `a-z`.
* `p` could be empty or contains only lowercase letters `a-z`, and characters like `?` or `*`.

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/wildcard-pattern-matching/)
* [Leetcode](https://leetcode.com/problems/wildcard-matching/)
* [ProgramCreek](https://www.programcreek.com/2014/06/leetcode-wildcard-matching-java/)
* [YouTube](https://youtu.be/3ZDZ-N0EPV0)

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** s = "aa", p = "a"

**Output:** false

**Explanation:** "a" does not match the entire string "aa".
{% endtab %}

{% tab title="Example 2" %}
**Input:** s = "aa", p = "\*"

**Output:** true

**Explanation:** '\*' matches any sequence.
{% endtab %}

{% tab title="Example 3" %}
**Input:** s = "cb", p = "?a"

**Output:** false

**Explanation:** '?' matches 'c', but the second letter is 'a', which does not match 'b'.
{% endtab %}

{% tab title="Example 4" %}
**Input:** s = "adceb", p = "*a*b"

**Output:** true

**Explanation:** The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
{% endtab %}

{% tab title="Example 5" %}
**Input:** s = "acdcb", p = "a\*c?b"

**Output:** false
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(min(S,P)) for the best case and better than O(SlogP) 
 *    for the average case, where S and P are lengths of the input string 
 *    and the pattern correspondingly.
 * Space complexity : O(1) since it's a constant space solution.
 */

class Solution {
    public boolean isMatch(String s, String p) {
        if(p.isEmpty()) return s.isEmpty();
        int sIndex = 0;
        int pIndex = 0;
        int starIndex = -1;
        int siIndex = -1;
        
        while(sIndex < s.length()) {
            if(pIndex < p.length() && 
               (p.charAt(pIndex) == '?' || s.charAt(sIndex) == p.charAt(pIndex))) {
                sIndex++;
                pIndex++;
            } else if(pIndex < p.length() && p.charAt(pIndex) == '*') {
                siIndex = sIndex;
                starIndex = pIndex;
                pIndex++;
            } else if(starIndex != -1) {
                sIndex = siIndex+1;
                pIndex = starIndex+1;
                siIndex++;
            } else {
                return false;
            }
        }
        
        while(pIndex < p.length() && p.charAt(pIndex) == '*') {
            pIndex++;
        }
        
        return pIndex == p.length();
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(SP) where S and P are lengths of the input string 
 *    and the pattern correspondingly.
 * Space complexity : O(SP) to keep the matrix.
 */

class Solution {
    public boolean isMatch(String s, String p) {
        if(p.equals(s) || p.equals("*")) return true;
        if(p.isEmpty() || s.isEmpty()) return false;

        int sLen = s.length(), pLen = p.length();
        boolean[][] dp = new boolean[sLen+1][pLen+1];
        dp[0][0] = true;
        
        for(int i = 1; i < pLen; i++) {
            if(p.charAt(i-1) == '*') {
                dp[0][i] = dp[0][i-1];
            }
        }
        
        for(int i = 1; i <= sLen; i++) {
            for(int j = 0; j <= pLen; j++) {
                if(j > 0 && 
                   (p.charAt(j-1) == '?' || p.charAt(j-1) == s.charAt(i-1))) {
                    dp[i][j] = dp[i-1][j-1];
                } else if(j > 0 && p.charAt(j-1) == '*') {
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                } else {
                    dp[i][j] = false;
                }
            }
        }
        
        return dp[sLen][pLen];
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

* Count the Number of matching characters in a pair of strings - [GFG](https://www.geeksforgeeks.org/count-the-number-of-matching-characters-in-a-pair-of-strings)