> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/44_wildcard_matching.md).

# 44 Wildcard Matching

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).

The function prototype should be: bool isMatch(const char *s, const char* p)

```
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
```

* Algorithm:
  * Store elements of the first string into an unordered map that maps each character with its frequency.
  * We dont need to store the elements of the second string into a hash set. Rather, we will simply iterate through it with precedence to be: "\[char]?\*".
    * The idea is to give most power to the \*, and least power to the \[chars]. That way, we priorities our most powerful characters last, and get rid of the least powerful first.
  * Now iterate through second string, and try to pair it with a char element from the first string. Ignore \* and ? for now.
    * If the pair is found and matched, decrement the frequency of the char from the hash\_set and erase the element from the second string. Otherwise, return false if the character is not found, or the frequency of the element is zero.
    * Next, iterate through to look for '?'. To do this, I will translate all the elements in the current unordered map (those of which that have a frequency > 0), into a priority queue of pairs of id . The pairs will be sorted from min to max using:
    * <http://stackoverflow.com/questions/26266136/how-do-you-keep-a-priority-queue-of-pairs-thats-ordered-by-the-second-element>
    * When we come across a '?', we decrement the frequency from the top of the priority queue of said element. If the said element reachs a frequency of zero, we remove it from the queue.
    * If the element is not found, we return false.
  * Now we preform the same algorithm in the priority queue, but in reverse, looking for \*. Here, we get rid of maxed out frequencies in the string first, removing them from the priority queue if queue is not empty(), and otherwise return false if it is.
* Finally, return true of the priority queue is empty() \[first string], and false otherwise.

```cpp
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/44_wildcard_matching.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.