Problem title
Difficulty
Avg time to solve

Smallest Number With At least N Trailing Zeros In Factorial
Easy
10 mins
Count Customers Who Did Not Get A Computer
Easy
15 mins
Reverse A Doubly Linked List
Easy
15 mins
K-th element of 2 sorted array
Hard
20 mins
Find pair with a given sum in a doubly linked list
Easy
10 mins
Check If Preorder Traversal Is Valid
Moderate
35 mins
Minimum Travel Time
Hard
35 mins
Print All Possible Paths From Top Left Corner To Bottom Right Corner Of A 2-D Matrix
Moderate
20 mins
Ninja And The Dance Competetion
Easy
10 mins
Fruits and Baskets
Hard
50 mins
6

Wildcard Queries

Difficulty: HARD
Contributed By
Avg. time to solve
50 min
Success Rate
55%

Problem Statement

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
Sample Input 1 :
2
5 3
cat
map
bat
man
pen
4
?at
ma?
?a?
??n
1 5
aaaaa
1
bbbbb
Sample Output 1 :
2
2
4
2
0
Explanation Of Sample Output 1 :
For test case 1 :
Query1: “?at” matches with “cat” and “bat”
Query2: “ma?” matches with “map” and “man”
Query3: “?a?” matches with “cat”, “bat”, “map” and “man”
Query4: “??n” matches with “man” and “pen”

For test case 2 :
Query1: “bbbbb” doesn’t matches with any dictionary words
Sample Input 2 :
2
5 3
cat
map
bat
man
pen
4
cat
ma?
?a?
pen
2 5
aaaaa
bbbbb
1
bbbbb
Sample Output 2 :
1
2
4
1
1
Reset Code
Full screen
copy-code
Console