题目如下:
Problem
After years of study, scientists at Google Labs have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.
Once the dictionary of all the words in the alien language was built, the next breakthrough was to discover that the aliens have been transmitting messages to Earth for the past decade. Unfortunately, these signals are weakened due to the distance between our two planets and some of the words may be misinterpreted. In order to help them decipher these messages, the scientists have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.
A pattern consists of exactly L tokens. Each token is either a single lowercase letter (the scientists are very sure that this is the letter) or a group of unique lowercase letters surrounded by parenthesis ( and ). For example: (ab)d(dc) means the first letter is either a or b, the second letter is definitely d and the last letter is either d or c. Therefore, the pattern (ab)d(dc) can stand for either one of these 4 possibilities: add, adc, bdd, bdc.
Input
The first line of input contains 3 integers, L, D and N separated by a space. D lines follow, each containing one word of length L. These are the words that are known to exist in the alien language. N test cases then follow, each on its own line and each consisting of a pattern as described above. You may assume that all known words provided are unique.
Output
For each test case, output
Case #X: K
where X is the test case number, starting from 1, and K indicates how many words in the alien language match the pattern.
Limits
Small dataset
1 ≤ L ≤ 10
1 ≤ D ≤ 25
1 ≤ N ≤ 10
Large dataset
1 ≤ L ≤ 15
1 ≤ D ≤ 5000
1 ≤ N ≤ 500
Sample
Input
3 5 4
abc
bca
dac
dbc
cba
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc
Output
Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0
这道题本身没有什么难度,唯一需要注意的就是速度了。
我的解法是找到每一个位(token)对应的单词的集合,然后将所有的集合做交集运算,最终结果集合的元素数量就是所求的结果。
为了快速找到每一个位所对应的单词集合,先便利单词的列表,为每一位建立一个从字母到单词集合的索引。
Index是一个包含了L个map容器的序列,每一个map容器对应一个位。每个map容器包含了从字母x到该位置的字母为x的映射。
这样从模式到单词可以简单的变换成集合操作。
如模式(ab)b(ac)对应的就是
wordSet = (index[0][a] | index[0][b]) & index[1][b] & (index[2][a] | index[2][c])
其中”|”是并集操作,”&”是交集操作。
Len(wordSet)就是要求的结果。
具体代码如下:
import sys
f = open(sys.argv[1])
L, D, N = [int(i) for i in f.readline().split()]
index = [{} for i in range(L)]
for i in range(D):
word = f.readline().strip()
offset = 0
for l in word:
if l not in index[offset]:
index[offset][l] = set()
index[offset][l].add(word)
offset += 1
for i in range(1, N+1):
testcase = f.readline().strip()
state = False
offset = 0
result = None
for l in testcase:
if l == '(':
state = True
s = set()
elif l == ')':
state = False
offset += 1
if result is None:
result = s
else:
result &= s
del s
else:
wordset = index[offset].get(l, set())
if state :
s |= wordset
else:
if not wordset: #wordset is an empty set
print("Case #%d: 0" % i)
break
if result is None:
result = wordset.copy()
else:
result &= wordset
if not result:
print("Case #%d: 0" % i)
break
offset += 1
else:
print("Case #%d: %d" % (i, len(result)))
f.close()
分享到:
相关推荐
自己写的源码,希望各位看官指出不足之处,好交流进步
PDF
2020-1 Bluetooth Qualification Program - Test Case Reference List(TCRLs)_2020-01-GATT-Audio_2020-BLP1.1-DTP-PAMP-ATP-CTES-MICP-CCP-TBS-MCP-MCS.zip.zip
2020-1 Bluetooth Qualification Program - Test Case Reference List(TCRLs)_2020-01-GATT-Audio_2020-BLP1.1-DTP-PAMP-ATP-CTES-MICP-CCP-TBS-MCP-MCS.zip.7z
JEDEC JEP143D:2019 Solid-State Reliability Assessment and Qualification Methodologies - 完整英文电子版(33页).pdf
ZVEI PCN-Delta-Qualification-Matrix-ZVEI-5_0_16.xlsm
java在线答疑源码 Google-Hash-Code-2020-Online-Qualification-Round Score
AEC - Q100 Rev H - QTP Template Qualification Test Plan - 完整英文电子版(4页).zip
Stress-Test-Driven Qualification of Integrated Circuits
AEC - Q104 QTP Template Qualification Test Plan - 完整英文电子版(5页).zip
JEDEC JEP155B:2018 Recommended ESD Target Level for HBM Qualification - 完整英文电子版(55页).pdf
EIA-944:2013 Surface Mount Ferrite Chip Bead Qualification Specification - 完整英文版(15页).zip
Qualification Rounds - 2015: B (Python) - 2016: A, C (C++) - 2017: A, B (C++) 3. Numerical Analysis Algorithms --- C - Newton-Raphson Root Finding Method - Simpson's Integration - Trapezoidal ...
JEDEC JEP172A:2015(R2020) Discontinuing Use of the Machine Model for Device ESD Qualification - 完整英文电子版(22页).pdf
JEDEC JESD47K-2018 Stress-Test-Driven Qualification of Integrated Circuits - 完整英文版(31页).pdf
完整英文版 IEC 61730-1:2023 Photovoltaic (PV) module safety qualification - Part 1:Requirements for construction(光伏(PV)组件安全资质第1部分:施工要求)。 IEC 61730-1:2023 规定并描述了光伏 (PV) ...
2015年CS游戏资格赛该目录包含 DCI 获得 2015 CS Games 资格所需的所有详细信息。介绍如果您接受它,您的任务将是开发一个比赛日程管理器。 每年,资格赛的组织者都会花费大量时间来尝试制定对所有参与者有吸引力的...
DO-178C对应的工具鉴定标准,DO-330.DO-330 Software Tool Qualification Considerations Mar 2012
AEC - Q200 Stress Test Qualification For Passive Components.zip
IEC 61215 Series - Terrestrial photovoltaic (PV) modules - Design qualification and type approval - 包含全部6份最新英文标准文件.7z