# 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
```