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^41 <= M <= 7 1 <= Q <= 10^5所以，这个问题我有 30 分钟的时间，我可以编写以下不正确的代码，因此没有给出预期的输出。

Answer 1

我想我的第一个尝试是在查询中用?a替换 the ，即更改为，然后将它们用作正则表达式并将它们与字典中的所有单词进行匹配，就像这样简单：.?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 4和 Q 到 10 5，这可能太慢了，就像比较所有单词和查询对的任何其他算法一样。

另一方面，请注意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) 如果查询是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_ {

    struct TrieNode_* nxt[26];

} TrieNode;

void addWord(TrieNode* root, string s) {

    TrieNode* node = root;

    for(int i = 0; i < s.size(); ++i) {

        if(node->nxt[s[i] - 'a'] == NULL) {

            node->nxt[s[i] - 'a'] = new TrieNode;

        }

        node = node->nxt[s[i] - 'a'];

    }

}

void matchCount(TrieNode* root, string s, int& cnt) {

    if(root == NULL) {

        return;

    }

    if(s.empty()) {

        ++cnt;

        return;

    }

    TrieNode* node = root;

    if(s[0] == '?') {

        for(int i = 0; i < 26; ++i) {

            matchCount(node->nxt[i], s.substr(1), cnt);

        }

    }

    else {

        matchCount(node->nxt[s[0] - 'a'], s.substr(1), cnt);

    }

}

int main() {

    int N, M;

    cin >> N >> M;

    vector<string> s(N);

    TrieNode *root = new TrieNode;

    for (int i = 0; i < N; ++i) {

        cin >> s[i];

        addWord(root, s[i]);

    }

    int Q;

    cin >> Q;

    for(int i = 0; i < Q; ++i) {

        string queryString;

        int cnt = 0;

        cin >> queryString;

        matchCount(root, queryString, cnt);

        cout << cnt << endl;

    }

}