title
按下述要求实现 StreamChecker 类：
StreamChecker(words)：构造函数，用给定的字词初始化数据结构。query(letter)：如果存在某些k >= 1，可以用查询的最后k个字符（按从旧到新顺序，包括刚刚查询的字母）拼写出给定字词表中的某一字词时，返回true。否则，返回false。
示例：
StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // 初始化字典
streamChecker.query('a'); // 返回 false
streamChecker.query('b'); // 返回 false
streamChecker.query('c'); // 返回 false
streamChecker.query('d'); // 返回 true，因为 'cd' 在字词表中
streamChecker.query('e'); // 返回 false
streamChecker.query('f'); // 返回 true，因为 'f' 在字词表中
streamChecker.query('g'); // 返回 false
streamChecker.query('h'); // 返回 false
streamChecker.query('i'); // 返回 false
streamChecker.query('j'); // 返回 false
streamChecker.query('k'); // 返回 false
streamChecker.query('l'); // 返回 true，因为 'kl' 在字词表中。
提示：
1 <= words.length <= 20001 <= words[i].length <= 2000- 字词只包含小写英文字母。
- 待查项只包含小写英文字母。
- 待查项最多 40000 个。
solution
class StreamChecker:
def __init__(self, words: List[str]):
self.trie = {}
for word in words:
node = self.trie
for c in reversed(word):
if c not in node:
node[c] = {}
node = node[c]
node['#'] = None
self.history = []
def query(self, letter: str) -> bool:
self.history.append(letter)
node = self.trie
for i in range(len(self.history) - 1, -1, -1):
c = self.history[i]
if c not in node:
return False
node = node[c]
if '#' in node:
return True
return False