Last Updated: 31 Jul, 2021
Wildcard Queries
Hard
Asked in company
You are given a dictionary ‘D’ consisting of ‘N’ words. Each word of the dictionary is of fixed size ‘L’ and contains only lowercase English alphabets.
Now you have to answer ‘Q’ queries, in each query you are given a word ‘W’ of fixed size ‘L’ but this word can consist of either lowercase English alphabets or ‘?’ (wildcard characters). Where ‘?’ can be matched by any lowercase English alphabet.
For each query find how many words in the dictionary can be matched by the query word ‘W’ by replacing ‘?’(if present) with some lowercase English alphabet.
Example :
If the dictionary is: {"cat", "rat", "bat", "hat"}
And query words are "?at" and "b?t", then:
"?at" => can be matched by all the 4 dictionary words by replacing '?' with 'c', 'r', 'b' or 'h'.
"b?t" => can only be matched by the dictionary word "bat" by replacing '?' with 'a'.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases. Then each test case follows.
The first line of each test case contains two integers ‘N’ and ‘L’, where N denotes the number of words in the dictionary and L denotes the length of words in the dictionary and queries.
The next line contains N words each of size L, denoting the words in the dictionary.
The next line contains a single integer ‘Q’ denoting the number of queries.
The following Q lines, each contains a word ‘W’ of size L, denoting the query word.
Output Format :
For each test case print Q integers in a separate line, each denoting the number of dictionary words that can be matched by the query word.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 100
1 <= L <= 7
1 <= Q <= 100
1 <= word.size <= L
Time limit: 1 sec
Approaches
Store the dictionary words in a hash-map for a constant lookup time, now for each query word, try replacing each ‘?’ with every possible lowercase alphabet and generating all possible words that can be formed by the query word, for each of them: search whether it exists in the dictionary or not.
The steps are as follows:
- Initialize finalAnswer array to store the answer to each query.
- Initialize a hash-map mp. And store all the dictionary words in it.
- For each query initialize count = 0 and generate all possible words that can be formed by replacing ‘?’ using backtracking.
- For each generated word, increment count if it exists in hash-map mp.
- Print the insert the value of count after generating all the words in the finalAnswer array.
- Move to the next query and repeat the same thing from 2nd Step.
- When all the queries have been processed return the finalAnswer array
Store the dictionary words using a trie data structure. Now process each query one at a time, for each query using Depth-First Search (dfs), transverse the trie and find all the possible words that can be matched by the current query word.
While implementing dfs, if the next node is a lower case alphabet then simply call dfs to the alphabet if it exists, but in case the next letter in query word ‘W’ is a wildcard (ie:’?’) then call dfs on all child nodes of the current node ( as ‘?’ can be replaced by any lowercase alphabet). Calculate the number of strings that be matched for each query.
The steps are as follows:
- Initialize finalAnswer array to store the answer of each query.
- Build a trie to store all the dictionary words.
- Now for each query word W, start dfs from the root node, and move to the next alphabet in W if it is a child of the current node.
- In case the next alphabet in W is ‘?’, then make a dfs call to all the child nodes of the current node in trie.
- For each query insert the matching words into finalAnswer array.
- When all the queries have been processed return the finalAnswer array
For each dictionary word, generate all possible words that can be matched to it by replacing some lowercase alphabets in it with a wildcard ‘?’. The maximum size of each word can be 7, and as each letter in the word has two options, whether it can be replaced by ‘?’ or not, hence 2^7 = 128 combinations are possible for each word. Generate all the combinations for each word and store its frequency in a hash-map. ( A hash-map word can be formed by multiple strings that is why we are storing the frequency, for example: “abc??d” can be formed from both “abcaad” and “abcbbd” if they are present in the dictionary)
Now for each query simply insert the frequency of the query word in the hash-map into the final answer array to be returned.
The steps are as follows:
- Initialize finalAnswer array to store the answer of each query.
- Initialize a hash-map mp. And store all the possible combinations of dictionary words in it.
- Generate all the possible combinations of each word in the dictionary using backtracking and insert each of them in hash-map mp.
- Now for each query word W, insert the frequency of W in the hash-map mp into the finalAnswer array.
- When all the queries have been processed return the finalAnswer array