谷歌编码挑战题2020：未指定的单词

Question

我在2020年8月16日发生的Google编码挑战赛中遇到了以下问题。我试图解决它，但没有成功。

字典中有N个单词，每个单词都是固定长度的，M只由小写英文字母组成，即（'a'，b'，…，'z'）
查询词由Q表示。查询词的长度为M。这些单词包含小写英文字母，但在某些地方不是字母介于“a”、“b”、…、'z’有'？' 。请参阅示例输入部分以了解这种情况

Q的匹配计数，由匹配计数（Q）表示，是字典中包含与查询词Q中字母相同位置的相同英文字母（不包括可以位于？位置的字母）的单词的计数。换句话说，词典中的一个单词可以包含位于'？'位置的任何字母 但其余字母必须与查询词匹配



给您一个查询词Q，您需要计算match\u count



输入格式

• 第一行包含两个空格分隔的整数N和M分别表示字典中的单词数和每个单词的长度。
• 接下来的N行分别包含字典中的一个单词。
• 下一行包含一个整数Q，表示必须计算match_count的查询字数。
• 接下来的Q行每行包含一个查询词。
  
  

输出格式对于每个查询词，在新行中打印特定词的match\u count

约束

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

它应该是O（N）时间和空间方法，因为M很小，可以认为是常数。您可能想在这里看看Trie的实现。

执行第一遍并将单词存储在Trie DS中。

接下来，按照以下顺序执行DFS和BFS的组合。

如果您收到一个？，执行BFS并添加所有子级。对于非？，执行DFS，这应该指向一个单词的存在。

为了进一步优化，后缀树也可用于存储DS。

Answer 2

这个问题可以在Trie数据结构的帮助下完成。首先将所有单词添加到trie ds中。然后你必须看看单词是否存在于trie中，有一个特殊的条件“？”所以你也必须注意这个条件，比如如果字符是？然后简单地转到单词的下一个字符。

我认为这种方法会奏效，Leetcode中也有类似的问题。

链接：https://leetcode.com/problems/design-add-and-search-words-data-structure/

Answer 3

匿名用户

我想我的第一次尝试是将查询中的？替换为.，即将？ 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到5x10⁴和Q到10⁵，这可能太慢了，就像任何其他算法比较所有单词和查询对一样。

另一方面，请注意，每个单词的字母数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）如果查询不包含任何？，只需检查它是否在单词的集中（！），而不创建所有这些交集；（b）如果查询是all-？，只需返回所有单词的集合；（c）按大小对可能的单词集进行排序，并首先使用最小的集合开始交集，以减少临时创建的集合的大小。

关于时间复杂度：老实说，我不确定这个算法的时间复杂度是多少。当N、Q和M分别为字数、查询数和字数和查询长度时，创建初始集的复杂性为O（N*M）。之后，查询的复杂性显然取决于非代码的数量 以及要创建的集合交点的数量，以及集合的平均大小。对于具有零、一或M非代码的查询 字符，查询将在O（M）中执行（评估情况，然后进行单个集合/字典查找），但对于具有两个或更多非代码的查询 -字符，第一组交叉点的平均复杂度为O（N/26），严格来说仍然是O（N）。（以下所有交叉口只需考虑N/26²、N/26³等要素，因此可以忽略不计。）我不知道这与Trie方法相比如何，如果其他任何答案能够详细说明这一点，我将非常感兴趣。