leetcode1032

 1 class StreamChecker:
 2     def __init__(self, words: 'List[str]'):
 3         self.maxLen = 0
 4         self.List = set(words)
 5         for w in self.List:
 6             self.maxLen = max(self.maxLen,len(w))
 7         self.STR = ''
 8 
 9     def query(self, letter: str) -> bool:
10 
11         if letter in self.List:
12             return True
13         else:
14             self.STR += letter
15             
16             clen = len(self.STR)
17             if clen > self.maxLen:
18                 self.STR = self.STR[1:]
19             
20             for w in self.List:
21                 lw = len(w)
22                 ls = len(self.STR)
23                 if ls >= lw and w == self.STR[ls-lw:]:
24                     return True
25             return False

此解决方案超时：

在上面的代码基础上，增加Trie数据结构，解决方案如下：

 1 class Node:
 2     def __init__(self):
 3         self.isWord = False
 4         self.next = [0]*26
 5 
 6 class StreamChecker:
 7     def __init__(self, words: 'List[str]'):
 8         self.maxLen = 0
 9         self.Trie = Node()
10         dwords = set(words)
11         for w in dwords:
12             cur = self.Trie
13             for i in range(len(w)-1,-1,-1):
14                 c = w[i]
15                 index = ord(c) - ord('a')
16                 if not cur.next[index]:
17                     cur.next[index] = Node()
18                 cur = cur.next[index]
19                 if i == 0:
20                     cur.isWord = True
21             self.maxLen = max(self.maxLen,len(w))
22         self.STR = ''
23 
24     def query(self, letter: str) -> bool:
25         self.STR += letter
26         clen = len(self.STR)
27         if clen > self.maxLen:
28                 self.STR = self.STR[1:]
29 
30         cur = self.Trie
31         for i in range(len(self.STR)-1,-1,-1):
32             c = self.STR[i]
33             index = ord(c) - ord('a')
34             if not cur.next[index]:
35                 return False
36             else:
37                 cur = cur.next[index]
38                 if cur.isWord:
39                     return True
40         return False