Last Updated: 12 Jan, 2021
Browser Query
Easy
Asked in company
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".
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
Approaches
- 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.
- Key observations as M is small that is 7 , for each website we can store all the strings that can possibly represent current websites.
- So if we are given a string “ab” then the queries “ab” , “a?” , “b?” , “??” can point to our string so we will maintain the count off all these strings in the hashmap.
- Let us say we currently have website S and let say we have query string T and we want to tell whether S matches T or not. S matches T only if S[i] == T[i] or T[i] == ‘?’ so for each position of S we have only two possible values. So for each website we can generate 2^M bit masks and in each bit mask replaces all 1 with ‘?’ at that index.
- Iterate through all the websites from 1 to N. Let's say we are currently at ith website.
- Take a temporary string S = website[i]
- Now iterate all 2^M masks.
- If the jth element of the mask is 1 then replace S[j] with ‘?’
- Increase count of S in a hashmap by 1.
- Now iterate through all the queries and print the count of that query from the hash map.
- For example if we have three websites that are “abc” , “aac” and “aba”.
- For “abc” we will have the following possible queries.
- “abc” , “ab?” , “a?c” , “a??” , “?bc” , “?b?” , “??c” , “???”
- For “aac” we will have the following possible queries.
- “aac” , “aa?” , “a?c” , “a??” , “?ac” , “?a?” , “??c” , “???”
- For “aba” we will have the following possible queries.
- “aba” , “ab?” , “a?a” , “a??” , “?ba” , “?b?” , “??a” , “???”
- Now if we ask the query of “ab?” it will answer 2. That is from the 1st and 3rd website.