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

Question

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

字典中有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 分钟的时间，我可以编写以下不正确的代码，因此没有给出预期的输出。

Answer 1

我想我的第一个尝试是在查询中用?a替换 the ，即更改为，然后将它们用作正则表达式并将它们与字典中的所有单词进行匹配，就像这样简单：.?at.atimport refor q in queries:&nbsp; &nbsp; p = re.compile(q.replace("?", "."))&nbsp; &nbsp; print(sum(1 for w in words if p.match(w)))但是，如果输入大小为 N 到 5x10 4和 Q 到 10 5，这可能太慢了，就像比较所有单词和查询对的任何其他算法一样。另一方面，请注意M，每个单词的字母数是恒定的且相当低。因此，您可以为所有位置的所有字母创建 Mx26 组单词，然后获取这些组的交集。from collections import defaultdictfrom functools import reduceM = 3words = ["cat", "map", "bat", "man", "pen"]queries = ["?at", "ma?", "?a?", "??n"]sets = defaultdict(set)for word in words:&nbsp; &nbsp; for i, c in enumerate(word):&nbsp; &nbsp; &nbsp; &nbsp; sets[i,c].add(word)all_words = set(words)for q in queries:&nbsp; &nbsp; possible_words = (sets[i,c] for i, c in enumerate(q) if c != "?")&nbsp; &nbsp; w = reduce(set.intersection, possible_words, all_words)&nbsp; &nbsp; print(q, len(w), w)在最坏的情况下（一个查询具有?字典中大多数或所有单词共有的非字母），这可能仍然很慢，但过滤单词应该比为每个查询迭代所有单词快得多。（假设单词和查询中都有随机字母，第一个字母的单词集将包含 N/26 个单词，前两个字母的交集有 N/26² 个单词，等等。）通过考虑不同的情况，这可能会有所改善，例如（a）如果查询不包含任何?，只需检查它是否在set单词的（！）中而不创建所有这些交集；(b) 如果查询是all- ?，只返回所有单词的集合；(c) 按大小对可能词集进行排序，并首先开始与最小集的交集，以减少临时创建的集的大小。关于时间复杂度：老实说，我不确定这个算法的时间复杂度是多少。N、Q 和 M 分别是单词数、查询数以及单词和查询的长度，创建初始集的复杂度为 O(N*M)。之后，查询的复杂性显然取决于查询中非查询的数量?（以及要创建的集合交集的数量）以及集合的平均大小。对于具有零个、一个或 M 个非?字符的查询，查询将在 O(M) 内执行（评估情况，然后进行单个集合/字典查找），但对于具有两个或更多非字符的查询?-字符，第一组交集的平均复杂度为 O(N/26)，严格来说仍然是 O(N)。（以下所有交叉点只需要考虑 N/26²、N/26³ 等元素，因此可以忽略不计。）我不知道这与 Trie 方法相比如何，如果其他任何答案可以详细说明，我将非常感兴趣在那上面。

Answer 2

这道题可以借助 Trie 数据结构来完成。首先将所有单词添加到 trie ds。然后你必须看看这个词是否存在于 trie 中，有一个特殊条件 ' ?' 所以你也必须注意这种情况，比如角色是？然后只需转到单词的下一个字符。

Answer 3

它应该是 O(N) 时间和空间方法，因为 M 很小并且可以被认为是常数。您可能想在这里查看 Trie 的实现。执行第一遍并将单词存储在 Trie DS 中。接下来对于您的查询，您按以下顺序执行 DFS 和 BFS 的组合。如果您收到 ?，请执行 BFS 并添加所有孩子。对于非 ?，执行 DFS，这应该指向一个词的存在。为了进一步优化，还可以使用后缀树来存储DS。

Answer 4

您可以使用简化版的 trie，因为查询字符串具有预定义的长度。endsTrie 节点中不需要变量#include <bits/stdc++.h>using namespace std;typedef struct TrieNode_ {&nbsp; &nbsp; struct TrieNode_* nxt[26];} TrieNode;void addWord(TrieNode* root, string s) {&nbsp; &nbsp; TrieNode* node = root;&nbsp; &nbsp; for(int i = 0; i < s.size(); ++i) {&nbsp; &nbsp; &nbsp; &nbsp; if(node->nxt[s[i] - 'a'] == NULL) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node->nxt[s[i] - 'a'] = new TrieNode;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; node = node->nxt[s[i] - 'a'];&nbsp; &nbsp; }}void matchCount(TrieNode* root, string s, int& cnt) {&nbsp; &nbsp; if(root == NULL) {&nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; }&nbsp; &nbsp; if(s.empty()) {&nbsp; &nbsp; &nbsp; &nbsp; ++cnt;&nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; }&nbsp; &nbsp; TrieNode* node = root;&nbsp; &nbsp; if(s[0] == '?') {&nbsp; &nbsp; &nbsp; &nbsp; for(int i = 0; i < 26; ++i) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; matchCount(node->nxt[i], s.substr(1), cnt);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; matchCount(node->nxt[s[0] - 'a'], s.substr(1), cnt);&nbsp; &nbsp; }}int main() {&nbsp; &nbsp; int N, M;&nbsp; &nbsp; cin >> N >> M;&nbsp; &nbsp; vector<string> s(N);&nbsp; &nbsp; TrieNode *root = new TrieNode;&nbsp; &nbsp; for (int i = 0; i < N; ++i) {&nbsp; &nbsp; &nbsp; &nbsp; cin >> s[i];&nbsp; &nbsp; &nbsp; &nbsp; addWord(root, s[i]);&nbsp; &nbsp; }&nbsp; &nbsp; int Q;&nbsp; &nbsp; cin >> Q;&nbsp; &nbsp; for(int i = 0; i < Q; ++i) {&nbsp; &nbsp; &nbsp; &nbsp; string queryString;&nbsp; &nbsp; &nbsp; &nbsp; int cnt = 0;&nbsp; &nbsp; &nbsp; &nbsp; cin >> queryString;&nbsp; &nbsp; &nbsp; &nbsp; matchCount(root, queryString, cnt);&nbsp; &nbsp; &nbsp; &nbsp; cout << cnt << endl;&nbsp; &nbsp; }}