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 modified 3yr ago