PYTHON
Implement a Trie (Prefix Tree) for Efficient String Operations
Build a Trie data structure in Python to store a dynamic set of strings, enabling very fast prefix searching, auto-completion, and spell-checking functionalities.
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
# Example Usage:
trie = Trie()
words_to_insert = ["apple", "apricot", "apply", "banana", "band"]
for word in words_to_insert:
trie.insert(word)
print(f"Search 'apple': {trie.search('apple')}") # True
print(f"Search 'app': {trie.search('app')}") # False (not marked as end of word)
print(f"Search 'apricot': {trie.search('apricot')}") # True
print(f"Search 'orange': {trie.search('orange')}") # 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 'ora': {trie.starts_with('ora')}") # False
print(f"Starts with 'apple': {trie.starts_with('apple')}") # True
How it works: A Trie (pronounced 'try'), also known as a prefix tree, is a tree-like data structure used to store a dynamic set of strings where each node stores a single character. By traversing from the root to a specific node, you can form a string. It's particularly efficient for operations involving prefixes, such as searching for words with a common prefix, auto-completion, or spell-checking, as it reduces redundant comparisons by sharing common prefixes among words.