1
class TrieNode:
2

3
    def __init__(self):
4
        self.children = {}
5
        self.endOfWord = False
6

7

8
class StreamChecker:
9

10
    def __init__(self, words: List[str]):
11
        self.root = TrieNode()
12
        self.qCur = self.root
13
        self.stream = collections.deque()
14
        cur = self.root
15
        for word in words:
16
            for i in range(len(word) - 1, -1, -1):
17
                ch = word[i]
18
                if ch not in cur.children:
19
                    cur.children[ch] = TrieNode()
20
                cur = cur.children[ch]
21
            cur.endOfWord = True
22
            cur = self.root
23

24
    def query(self, letter: str) -> bool:
25
        self.stream.appendleft(letter)
26
        cur = self.root
27
        for ch in self.stream:
28
            if ch not in cur.children:
29
                return False
30
            else:
31
                cur = cur.children[ch]
32
                if cur.endOfWord:
33
                    return True
34
        return False