Browser Query

Easy

0/40

Average time to solve is 15m

Contributed by

7 upvotes

Asked in company

Problem statement

The Ninjanet of Ninjaland has N websites. The name of all websites is in the form of a string and all of them have a length equal to M. Ayush is searching for his favourite website but unfortunately, he forgot some of the characters of the website so he replaced those characters with ‘?’. Your task is to calculate the number of websites that can possibly be a favourite of Ayush.

For example:

There are three websites in Ninjanet that are: "abc", "aba" and "aac".

If Ayush searches for “ab?” then there will be 2 websites that could be a favourite of Ayush, which are "abc" and "aba".

If Ayush searches for “?a?” then there will be only 1 website that could be a favourite of Ayush, i.e. "aac".

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains three space-separated integers N, M and Q, denoting the number of websites, length of each website and number of queries respectively.

Next, the N line contains a single string,  where the ith line consists of the name of the ith website in the Ninjanet.

Next, the Q line contains a query string, the name of the favourite website of Ayush with certain ‘?’ characters (Possibly 0), as described in the problem statement.

Output format :

For each query, print a single integer on a newline, denoting the number of websites that can possibly be Ayush’s favourite website.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraint :

1 <= N <= 10^4
1 <= M <= 6
1 <= Q <= 10^5

Time Limit: 1 sec

Sample Input 1 :

5 3 5
cat
map
cam
eat
fat
?at
ca?
?a?
??t
???

Sample Output 1 :

Explanation For Sample Input 1 :

For the first query, there are 3 possible favourite websites that are “cat” , “eat” and “fat”.
For the second query , there are 2 possible favourite websites that are “cat” , “cam”.
For the third query , all the websites have ‘a’ at their 2nd place so all are possible favourites.
For the fourth query , there are 3 possible favorite websites that are  “cat” , “eat” and “fat”.
For the fifth query , all the websites can be possible favourites.

Sample Input 2 :

3 3 2
abc
aac
aba
ab?
?a?

Sample Output 2 :

2
1

Hint 1

Hint 2

Try to compare query with every website

Approaches (2)

Approach 1

Approach 2

Bruteforce

In this approach we will match each query to each of the websites and print all the strings that matched to it.
For each query we will maintain a variable count which would initially be zero.
Now iterate through all the websites from 1 to N.
- If the query matches the website i then increase the count by 1.
Print the count for each query.

Time Complexity

O(N * M * Q), where N is the number of websites, M is the size of each website and Q is the number of queries.

Because we are matching the query with N websites of length M and there are Q such queries.

Space Complexity

O(1)

As we are using constant extra space.

(100% EXP penalty)

Browser Query

Console