LeetCode: 1032. Stream of Characters

First thing I came out with was to use a trie data structure, as it helps us deal with characters efficiently.

class StreamChecker:

    def __init__(self, words: List[str]):
        self.trie = {}
        for word in words:
            node = self.trie
            for char in word:
                if char not in node:
                    node[char] = {}
                node = node[char]
            node['#'] = '#'
        self.candidates = []

    def query(self, letter: str) -> bool:
        self.candidates.append(self.trie)
        next_candidates = []
        ret = False
        for candidate in self.candidates:
            if letter in candidate:
                next_candidates.append(candidate[letter])
                if '#' in candidate[letter]:
                    ret = True
        self.candidates = next_candidates
        return ret


# Your StreamChecker object will be instantiated and called as such:
# obj = StreamChecker(words)
# param_1 = obj.query(letter)

However, above code is very inefficient because it stores evey possible string that has the current letter in the middle of itself. 

To avoid this, we have to make great use of the fact that the only thing we have to do is check whether there's a word that ends with the current letter.

So, we make a trie with reversed words and everytime query function is called we just go through the trie.

class StreamChecker:

    def __init__(self, words: List[str]):
        self.trie = {}
        for word in words:
            node = self.trie
            for char in word:
                if char not in node:
                    node[char] = {}
                node = node[char]
            node['#'] = '#'
        self.candidates = []

    def query(self, letter: str) -> bool:
        self.candidates.append(self.trie)
        next_candidates = []
        ret = False
        for candidate in self.candidates:
            if letter in candidate:
                next_candidates.append(candidate[letter])
                if '#' in candidate[letter]:
                    ret = True
        self.candidates = next_candidates
        return ret


# Your StreamChecker object will be instantiated and called as such:
# obj = StreamChecker(words)
# param_1 = obj.query(letter)