PYTHON
Implement a Trie (Prefix Tree) for Autocomplete
Build an efficient Trie data structure in Python for fast prefix-based searches, useful for implementing autocomplete features or dictionary lookups in web applications.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def starts_with(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
def _find_all_words_from_node(self, node, prefix, words):
if node.is_end_of_word:
words.append(prefix)
for char, child_node in node.children.items():
self._find_all_words_from_node(child_node, prefix + char, words)
def autocomplete(self, prefix: str) -> list[str]:
node = self.root
for char in prefix:
if char not in node.children:
return [] # No words with this prefix
node = node.children[char]
results = []
self._find_all_words_from_node(node, prefix, results)
return results
# Example Usage:
trie = Trie()
trie.insert("apple")
trie.insert("apply")
trie.insert("app")
trie.insert("apricot")
trie.insert("banana")
print(f"Search 'apple': {trie.search('apple')}") # True
print(f"Search 'app': {trie.search('app')}") # True
print(f"Search 'apps': {trie.search('apps')}") # False
print(f"Starts with 'app': {trie.starts_with('app')}") # True
print(f"Starts with 'ban': {trie.starts_with('ban')}") # True
print(f"Starts with 'gra': {trie.starts_with('gra')}") # False
print(f"Autocomplete 'ap': {trie.autocomplete('ap')}") # ['apple', 'apply', 'app', 'apricot']
print(f"Autocomplete 'app': {trie.autocomplete('app')}") # ['apple', 'apply', 'app']
print(f"Autocomplete 'ba': {trie.autocomplete('ba')}") # ['banana']
print(f"Autocomplete 'gra': {trie.autocomplete('gra')}") # []
How it works: This snippet implements a Trie (also known as a prefix tree), a tree-like data structure used for efficient retrieval of a key in a dataset of strings. Each node typically stores a character, and paths from the root to a node represent a prefix. It's highly effective for tasks like autocomplete, spell-checking, and dictionary searches in web applications. The `insert` method adds words, `search` checks for a full word, `starts_with` checks for a prefix, and `autocomplete` finds all words with a given prefix.