2020 年 Google 编程挑战题：未指明的词

Question

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

有N在字典中，使得每个字的长度是固定的和词语M仅由小写英文字母，即 ('a', 'b', ...,'z')
一个查询字由表示Q。查询词的长度为M。这些单词包含小写英文字母，但在某些地方，而不是中间'a', 'b', ...,'z' 有一个字母'?'。请参阅示例输入部分以了解这种情况。

的匹配计数Q，表示match_count(Q)为字典中包含?与查询单词中的字母相同位置的相同英文字母（不包括可以位于位置的字母）的单词数Q。换句话说，字典中的一个词可以在'?' 但剩余的字母必须与查询词匹配。

给你一个查询词 Q，你需要计算 match_count。

输入格式

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

输出格式
对于每个查询词，match_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

我想我的第一次尝试?是.在查询中用 a替换，即更改?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) 如果查询不包含 any ?，只需检查它是否在set单词 (!) 中，而不创建所有这些交集；(b) 如果查询是 all- ?，只返回所有单词的集合；(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 相比如何，如果任何其他答案可以详细说明，我会非常感兴趣在那。

Answer 2

这个问题可以在 Trie Data Structures 的帮助下完成。首先将所有单词添加到 try ds。然后你必须看看这个词是否出现在 trie 中，有一个特殊的条件 '?' 所以你也必须注意这种情况，比如角色是 ? 然后只需转到单词的下一个字符即可。

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

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