Interview frequency: …
Short answer
A Trie stores strings character by character so words with the same prefix share a path, allowing lookup and prefix retrieval in O(L), where L is the word length, independent of the number of stored words.
Explanation
With a hash table, you need the complete word to calculate its hash, and you cannot find every word beginning with "car" without scanning every table entry in O(N). In a Trie, you reach nodes "c", "a", then "r" in just three steps, then traverse the subtree to immediately get all autocomplete suggestions.
Code example
class Trie:
def __init__(self):
self.children, self.is_word = {}, False
def insert(self, word):
node = self
for ch in word:
node = node.children.setdefault(ch, Trie())
node.is_word = True
def with_prefix(self, prefix):
node = self
for ch in prefix: # O(len(prefix)), independent of how many words exist
if ch not in node.children:
return []
node = node.children[ch]
found = []
def walk(n, path):
if n.is_word:
found.append(prefix + path)
for ch, child in n.children.items():
walk(child, path + ch)
walk(node, "")
return found
trie = Trie()
for word in ("car", "cat", "dog"):
trie.insert(word)
print(trie.with_prefix("ca")) # ['car', 'cat']Common mistakes
- High memory use in a standard Trie because of many empty pointers; address this with a Radix Tree or Compressed Trie.