-
-
Notifications
You must be signed in to change notification settings - Fork 298
/
Copy path676.py
95 lines (78 loc) · 2.75 KB
/
676.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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
__________________________________________________________________________________________________
sample 28 ms submission
class TrieNode(object):
def __init__(self):
self.children = {}
self.isword = False
self.word = None
class Trie(object):
def __init__(self):
self.root = TrieNode()
def add(self, w):
p = self.root
for c in w:
if c not in p.children:
p.children[c] = TrieNode()
p = p.children[c]
p.isword = True
p.word = w
def prefix(self, w):
p = self.root
for c in w:
if c not in p.children:
return None
p = p.children[c]
return p
def search(self, w):
p = self.root
def dfs(word, nd, cnt):
if cnt > 1 or not word:
return cnt == 1 and nd.isword
return any([dfs(word[1:], nd.children[c], cnt+(c!=word[0])) for c in nd.children])
return dfs(w, p, 0)
class MagicDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.T = Trie()
def buildDict(self, dict: List[str]) -> None:
"""
Build a dictionary through a list of words
"""
for w in dict:
self.T.add(w)
def search(self, word: str) -> bool:
"""
Returns if there is any word in the trie that equals to the given word after modifying exactly one character
"""
return self.T.search(word)
# Your MagicDictionary object will be instantiated and called as such:
# obj = MagicDictionary()
# obj.buildDict(dict)
# param_2 = obj.search(word)
__________________________________________________________________________________________________
sample 32 ms submission
class MagicDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.buckets = collections.defaultdict(list)
def buildDict(self, dict: List[str]) -> None:
"""
Build a dictionary through a list of words
"""
for w in dict:
self.buckets[len(w)].append(w)
def search(self, word: str) -> bool:
"""
Returns if there is any word in the trie that equals to the given word after modifying exactly one character
"""
return any(sum(a!=b for a, b in zip(word, candidate))==1
for candidate in self.buckets[len(word)])
# Your MagicDictionary object will be instantiated and called as such:
# obj = MagicDictionary()
# obj.buildDict(dict)
# param_2 = obj.search(word)
__________________________________________________________________________________________________