python - 2020 年 Google 编程挑战题 : Unspecified Words

Question

我在 2020 年 8 月 16 日的 Google Coding Challenge 中遇到了以下问题。我试图解决它，但无法解决。

There are N words in a dictionary such that each word is of fixed length and M consists only of lowercase English letters, that is ('a', 'b', ...,'z')
A query word is denoted by Q. The length of query word is 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 of '?' 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.

Input Format

• The 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 query word, print match_count for a specific word in a new line.

Constraints

1 <= N <= 5X10^4
1 <= M <= 7 
1 <= Q <= 10^5

所以，我有 30 分钟的时间回答这个问题，我可以编写以下不正确的代码，因此没有给出预期的输出。

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)

有人可以帮我提供一些可以解决这个问题的伪代码或算法吗？

Answer 1

我想我的第一次尝试是更换 ?与 .在查询中，即更改 ?at至 .at ，然后将它们用作正则表达式并将它们与字典中的所有单词进行匹配，就像这样简单:

import re
for q in queries:
    p = re.compile(q.replace("?", "."))
    print(sum(1 for w in words if p.match(w)))

但是，将输入大小视为 N 高达 5x104 和 Q 高达 105，这可能太慢了，就像任何其他算法比较所有单词和查询对一样。
另一方面，请注意 M ，每个单词的字母数，是常数且相当低。因此，您可以为所有位置的所有字母创建 Mx26 组单词，然后获取这些组的交集。

from collections import defaultdict
from functools import reduce

M = 3
words = ["cat", "map", "bat", "man", "pen"]
queries = ["?at", "ma?", "?a?", "??n"]

sets = defaultdict(set)
for word in words:
    for i, c in enumerate(word):
        sets[i,c].add(word)

all_words = set(words)
for q in queries:
    possible_words = (sets[i,c] for i, c in enumerate(q) if c != "?")
    w = reduce(set.intersection, possible_words, all_words)
    print(q, len(w), w)

在最坏的情况下(查询的非 ? 字母对字典中的大多数或所有单词都很常见)这可能仍然很慢，但过滤单词应该比迭代所有单词快得多每个查询。 (假设单词和查询中的字母都是随机的，第一个字母的单词集将包含 N/26 个单词，前两个的交集包含 N/26² 个单词等)
通过考虑不同的情况，这可能会有所改善，例如(a) 如果查询不包含任何 ? ，只要检查它是否在set中(!) 没有创建所有这些交集的单词； (b) 如果查询全部是- ? , 只返回所有单词的集合； (c) 按大小对可能的词集进行排序，并首先从最小的集开始交集，以减少临时创建的集的大小。
关于时间复杂度:老实说，我不确定这个算法的时间复杂度是多少。 N、Q 和 M 分别是单词数、查询数以及单词和查询的​​长度，创建初始集合的复杂度为 O(N*M)。之后，查询的复杂度显然取决于非?的数量。在查询中(以及要创建的集合交集的数量)，以及集合的平均大小。对于具有零、一或 M 非 ? 的查询字符，查询将在 O(M) 中执行(评估情况，然后进行单个 set/dict 查找)，但对于具有两个或多个非 ? 的查询-characters，第一组交集的平均复杂度为 O(N/26)，严格来说仍然是 O(N)。 (以下所有交叉点只需要考虑 N/26²、N/26³ 等元素，因此可以忽略不计。)我不知道这与 The Trie Approach 相比如何，如果任何其他答案可以详细说明，我会非常感兴趣在那。