-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
745.py
53 lines (46 loc) · 1.92 KB
/
745.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
__________________________________________________________________________________________________
sample 716 ms submission
class WordFilter:
def __init__(self, words):
from collections import defaultdict
self.prefixes = defaultdict(set)
self.suffixes = defaultdict(set)
self.weights = {}
for index, word in enumerate(words):
prefix, suffix = '', ''
for char in [''] + list(word):
prefix += char
self.prefixes[prefix].add(word)
for char in [''] + list(word[::-1]):
suffix += char
self.suffixes[suffix[::-1]].add(word)
self.weights[word] = index
def f(self, prefix, suffix):
weight = -1
for word in self.prefixes[prefix] & self.suffixes[suffix]:
if self.weights[word] > weight:
weight = self.weights[word]
return weight
__________________________________________________________________________________________________
sample 748 ms submission
class WordFilter:
def __init__(self, words: List[str]):
self.filters = {}
for idx, word in enumerate(words):
n = len(word)
prefixes = ['']*(n+1)
suffixes = ['']*(n+1)
for i in range(n):
prefixes[i+1] = prefixes[i] + word[i]
suffixes[i+1] = word[n-i-1] + suffixes[i]
for pre in prefixes:
for suf in suffixes:
self.filters[pre + '_' + suf] = idx
def f(self, prefix: str, suffix: str) -> int:
key = prefix + '_' + suffix
if key in self.filters: return self.filters[key]
return -1
# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(prefix,suffix)
__________________________________________________________________________________________________