title: Google Coding Challenge Question 2020 : Unspecified Words
body: <p><br><em>I got the following problem for the Google Coding Challenge which happened on 16th August 2020. I tried to solve it but couldn't.</em> <br><br></p>
  <blockquote>
  <p>There are <code>N</code> words in a dictionary such that each word is of fixed
  length and <code>M</code> consists only of lowercase English letters, that is
  <code>('a', 'b', ...,'z')</code><br> A query word is denoted by <code>Q</code>. The length
  of query word is <code>M</code>. These words contain lowercase English letters
  but at some places instead of a letter between <code>'a', 'b', ...,'z'</code>
  there is <code>'?'</code>. Refer to the Sample input section to understand this
  case. <br><br> A match count of <code>Q</code>, denoted by <code>match_count(Q)</code> 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 <code>?</code>) in the
  same position as the letters are there in the query word <code>Q</code>. In other
  words, a word in the dictionary can contain any letters at the
  position of <code>'?'</code> but the remaining alphabets must match with the
  query word.<br><br></p>
  <p>You are given a query word Q and you are required to compute
  <code>match_count</code>.<br><br></p>
  <p><strong>Input Format</strong> <br></p>
  <ul>
  <li>The first line contains two space-separated integers <code>N</code> and <code>M</code> denoting the number of words in the dictionary and length of each word
  respectively.</li>
  <li>The next <code>N</code> lines contain one word each from the dictionary.</li>
  <li>The next line contains an integer Q denoting the number of query words for which you have to compute match_count.</li>
  <li>The next <code>Q</code> lines contain one query word each. <br><br></li>
  </ul>
  <p><strong>Output Format</strong>  <br> For each query word, print <code>match_count</code> for a specific word in a new line. <br><br>
  <strong>Constraints</strong> <br></p>
  <pre><code>1 &lt;= N &lt;= 5X10^4
  1 &lt;= M &lt;= 7 
  1 &lt;= Q &lt;= 10^5
  </code></pre>
  </blockquote>
  <p><a href="https://i.stack.imgur.com/3Tifp.png" rel="noreferrer"><img src="https://i.stack.imgur.com/3Tifp.png" alt="enter image description here" /></a></p>
  <p><a href="https://i.stack.imgur.com/lG0rD.png" rel="noreferrer"><img src="https://i.stack.imgur.com/lG0rD.png" alt="enter image description here" /></a></p>
  <p><a href="https://i.stack.imgur.com/OTpzc.png" rel="noreferrer"><img src="https://i.stack.imgur.com/OTpzc.png" alt="enter image description here" /></a></p>
  <p><br>
  So, I got 30 minutes for this question and I could write the following code which is incorrect and hence didn't give the expected output.
  <br><br></p>
  <pre><code>def Solve(N, M, Words, Q, Query):
      output = []
      count = 0
      for i in range(Q):
          x = Query[i].split('?')
          for k in range(N):
              if x in Words:
                 count += 1
              else:
                  pass
          output.append(count)
      return output
  
  N, M = map(int , input().split())
  Words = []
  for _ in range(N):
      Words.append(input())
  
  Q = int(input())
  Query = []
  for _ in range(Q):
      Query.append(input())
  
  out =  Solve(N, M, Words, Q, Query)
  for x in out_:
      print(x)
  </code></pre>
  <p><em>Can somebody help me with some pseudocode or algorithm which can solve this problem, please?</em></p>