44 Wildcard Matching
Last updated
Was this helpful?
Last updated
Was this helpful?
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)
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.