字典树（前缀树）
class Trieroot:
def __init__(self):
self.isEnd = False
self.next = {}
self.pre = ""
self.count = 0
class Trie:
def __init__(self):
self.root = Trieroot()
def insert(self, word: str) -> None:
node = self.root
for st in word:
ind = ord(st)-ord('a')
if ind not in node.next:
node.next[ind] = Trieroot()
node = node.next[ind]
node.isEnd = True
node.count +=1
node.pre = word
def search(self, word: str) -> bool:
node = self.root
for st in word:
ind = ord(st)-ord('a')
if ind not in node.next:
return False
node = node.next[ind]
return node.isEnd
def startsWith(self, prefix: str) -> bool:
def find(node):
if node.isEnd:
save[node.pre] = node.count
if not node.next:
return
for ind in node.next:
find(node.next[ind])
node = self.root
for st in prefix:
ind = ord(st)-ord('a')
if ind not in node.next:
return False
node = node.next[ind]
save = {}
find(node)
print(save)
print(sorted(save,reverse=True))
# Your Trie object will be instantiated and called as such:
obj = Trie()
obj.insert("apple")
obj.insert("apple")
obj.insert("apple")
obj.insert("apple")
obj.insert("app")
obj.insert("app")
obj.insert("app")
obj.insert("sopo")
obj.insert("apm")
obj.search("app")
obj.startsWith("a") #华为面试#
