LeetCode 字典树与哈希表对比题解

LeetCode 字典树与哈希表对比题解

题目描述

对比字典树和哈希表的优缺点。

字典树 vs 哈希表

字典树的优点

1. 高效的前缀查询
2. 有序输出
3. 空间共享

字典树的缺点

1. 实现复杂
2. 占用空间较大

哈希表的优点

1. 实现简单
2. 查询效率高
3. 占用空间较小

哈希表的缺点

1. 无法高效处理前缀查询
2. 无法有序输出

代码实现

# 字典树实现 class TrieNode: def __init__(self): self.children = {} self.is_end = False class Trie: def __init__(self): self.root = TrieNode() def insert(self, word): node = self.root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.is_end = True def search(self, word): node = self.root for char in word: if char not in node.children: return False node = node.children[char] return node.is_end # 哈希表实现 class HashTable: def __init__(self): self.table = {} def insert(self, word): self.table[word] = True def search(self, word): return word in self.table # 测试 def test_comparison(): trie = Trie() trie.insert("apple") print(trie.search("apple")) # 输出：True ht = HashTable() ht.insert("apple") print(ht.search("apple")) # 输出：True if __name__ == "__main__": test_comparison()

总结

字典树和哈希表各有优缺点，应根据具体问题选择合适的数据结构。