Hello everyone, I am stuck at this problem. I think we can use a Trie. But I am unable to handle the special character '?'. Please help me with this problem. Thanks in advance :).
There are N words in a dictionary such that each word is of fixed length M, and consists of only lower case english alphabets. A query word Q also has length M. Query word also contains only lower case english alphabets but at some places instead of an alphabet it has "?". match_count of Q, is the count of words in the dictionary (already populated with words of same length M) and contains the same english letters (excluding the letter that can be in the position of ?) in the same position as the letters are there in the query word Q. Your are given the query word Q and you have to find the match_count.
Input Format
First line contains two space seperated integers N and M denoting the number of words in the dictionary and the length of each word
Next N line contains the words in the dictionary
Next line Q contains the number of query words
Next Q lines contain one query word each
Output
For each query word output the match_count
Constrains
1<=N<=5x10^4
1<=M<=7
1<=Q<=10^5
Time Limit - 4 secs
Sample Input:
5 3
cat
map
bat
man
pen
4
?at
ma?
?a?
??n
Sample Output
2
2
4
2
