一种字典树的Python实现

字典树，也叫单词查找树，Trie, 是一种自定义的树形数据结构，用于统计、排序和保存大量的字符串，利用字符串的公共前缀来减少查询时间和存储空间，查找效率比哈希树高。
字典树应该支持的操作：插入 查找 前缀 移除 展示：
insert(word): Insert a word into the Trie
search(word): Return if the word in the Trie
startsWith(prefix): Return if there is any words in the trie that starts with the given prefix
remove(word): Remove word from the Trie
show(): Print the architecture of the Trie using indents

Python实现

class Trie:def __init__(self):"""Initialize your data structure here."""self.dic = {}def insert(self, word: str) -> None:"""Inserts a word into the trie."""tree = self.dicfor i in word:tree = tree.setdefault(i, {})tree['#'] = '#'def search(self, word: str) -> bool:"""Returns if the word is in the trie."""tree = self.dicfor i in word:if i not in tree:return Falsetree = tree[i]return '#' in treedef startsWith(self, prefix: str) -> bool:"""Returns if there is any word in the trie that starts with the given prefix."""tree = self.dicfor i in prefix:if i not in tree:return Falsetree = tree[i]return Truedef remove(self, word: str) -> None:"""Remove the word from the Trie."""def _remove_helper(node, word, index):if index == len(word):# 找到单词末尾，删除结束标记if '#' in node:del node['#']return len(node) == 0  # 如果节点没有其他子节点，可以删除char = word[index]if char not in node:return False  # 单词不存在should_delete = _remove_helper(node[char], word, index + 1)if should_delete:del node[char]return len(node) == 0  # 检查当前节点是否可以删除_remove_helper(self.dic, word, 0)def show(self):"""以缩进形式层次化展示Trie树结构"""def _show_helper(node, level=0):for key, child in node.items():if key == '#':print('  ' * level + '# (end)')else:print('  ' * level + key)_show_helper(child, level + 1)_show_helper(self.dic)