leetcode1032

╰+哭是因爲堅強的太久メ 2021-12-19 04:09 180阅读 0赞

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

此解决方案超时：

![956600-20190421141130662-205233847.png][]

在上面的代码基础上，增加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

转载于:https://www.cnblogs.com/asenyang/p/10745020.html

[956600-20190421141130662-205233847.png]: /images/20211218/ad096eb58acb446288dd1983888306f5.png