gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-03 07:29:10 24 4
gpt4 key购买 nike

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

There are N words in a dictionary such that each word is of fixedlength and M consists only of lowercase English letters, that is('a', 'b', ...,'z')
A query word is denoted by Q. The lengthof query word is M. These words contain lowercase English lettersbut at some places instead of a letter between 'a', 'b', ...,'z'there is '?'. Refer to the Sample input section to understand thiscase.

A match count of Q, denoted by match_count(Q) is thecount of words that are in the dictionary and contain the same Englishletters(excluding a letter that can be in the position of ?) in thesame position as the letters are there in the query word Q. In otherwords, a word in the dictionary can contain any letters at theposition of '?' but the remaining alphabets must match with thequery word.

You are given a query word Q and you are required to computematch_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 wordrespectively.
  • 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

enter image description here
enter image description here
enter image description here

所以,我有 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)
有人可以帮我提供一些可以解决这个问题的伪代码或算法吗?

最佳答案

我想我的第一次尝试是更换 ?.在查询中,即更改 ?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 相比如何,如果任何其他答案可以详细说明,我会非常感兴趣在那。

关于python - 2020 年 Google 编程挑战题 : Unspecified Words,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63472161/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com