Unspecified Words There are N words in a dictionary such that | Cse interview questions

Unspecified Words

There are N words in a dictionary such that each word is of fixed length M and consists of only lowercase English letters that are ('a', 'b', ... , 'z').

A query word is denoted by Q. The length of query word in M. These words contain lowercase English letters but at some places instead of a letter between 'a', 'b', ... , 'z' there is '?'. Refer to the Sample input section to understand this case.

A match count of Q, denoted by match_count(Q), is the count of words that are in the dictionary and contain the same English letters (excluding a letter that can be in the position of ?) in the same position as the letters are there in the query word Q.

In other words, a word in the dictionary can contain any letters at the position '?' but the remaining alphabets must match with the query word.

You are given a query word Q and you are required to compute match_count(Q).

Input format :

First-line contains two space-separated integers N and M denoting the number of words in the dictionary and length of each word respectively.

The next N lines contain one word each from the dictionary.

The next line contains an integer Q denoting the number of query words for which you have to compute match_count().

The next Q lines contain one query word each.

Output Format :

For each of the query word, print match_count in a new line.

Constraints :

1 ≤ N ≤ 5 x 10^4
1 ≤ M ≤ 7
1 ≤ Q ≤ 10^5

Sample Input :

5 3
cat
map
bat
man
pen
4
?at
ma?
?a?
??n

Sample Output :

2
2
4
2

Explanation for Sample Input :

The two space-separated integers in first line denotes 5 dictionary words, each of length 3 letters. Next 5 lines contain those five words.

Next line containing an integer 4 denotes four queries for which match_count() has to be computed. Then those query words follows in next four lines.

Explanation for Sample Output :

?at
cat and bat end with 'at'.
match count = 2

ma?
map and man start with 'ma'
match count = 2

?a?
cat, map, bat and man have 'a' as their middle letter.
match count = 4

??n
man and pen end with 'n'
match count = 2

Topic : Strings

Reference(s) ->
GeeksforGeeks, Chegg

Solution ->
Ideas can be borrowed from
Stack Overflow, Codeforces blog

Asked in Google

Join our Official Channel @cseinterview