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:

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

Last updated