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.