-
Notifications
You must be signed in to change notification settings - Fork 26
/
1032.StreamofCharacters.py
86 lines (74 loc) · 3.1 KB
/
1032.StreamofCharacters.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
"""
Implement the StreamChecker class as follows:
- StreamChecker(words): Constructor, init the data structure with the
given words.
- query(letter): returns true if and only if for some k >= 1, the last
k characters queried (in order from oldest to newest, including this
letter just queried) spell one of the words in the given list.
Example:
StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]);
// init the dictionary.
streamChecker.query('a'); // return false
streamChecker.query('b'); // return false
streamChecker.query('c'); // return false
streamChecker.query('d'); // return true, because 'cd' is in the
// wordlist
streamChecker.query('e'); // return false
streamChecker.query('f'); // return true, because 'f' is in the
// wordlist
streamChecker.query('g'); // return false
streamChecker.query('h'); // return false
streamChecker.query('i'); // return false
streamChecker.query('j'); // return false
streamChecker.query('k'); // return false
streamChecker.query('l'); // return true, because 'kl' is in the
// wordlist
Note:
- 1 <= words.length <= 2000
- 1 <= words[i].length <= 2000
- Words will only consist of lowercase English letters.
- Queries will only consist of lowercase English letters.
- The number of queries is at most 40000.
"""
#Difficulty: Hard
#17 / 17 test cases passed.
#Runtime: 1132 ms
#Memory Usage: 42.9 MB
#Runtime: 1132 ms, faster than 44.37% of Python3 online submissions for Stream of Characters.
#Memory Usage: 42.9 MB, less than 11.57% of Python3 online submissions for Stream of Characters.
class Trie:
def __init__(self):
self.children = [None] * 26
self.is_word = False
def addWord(self, word):
current = self
i = len(word) - 1
while i >= 0:
index = ord(word[i]) - 97
if not current.children[index]:
current.children[index] = Trie()
current = current.children[index]
i -= 1
current.is_word = True
class StreamChecker:
def __init__(self, words: List[str]):
self.stack = []
self.words = Trie()
for word in words:
self.words.addWord(word)
def query(self, letter: str) -> bool:
self.stack.append(letter)
current = self.words
pop = len(self.stack) - 1
while pop >= 0:
index = ord(self.stack[pop]) - 97
if current.is_word:
return True
if not current.children[index]:
return False
current = current.children[index]
pop -= 1
return current.is_word
# Your StreamChecker object will be instantiated and called as such:
# obj = StreamChecker(words)
# param_1 = obj.query(letter)