class TrieNode:
def __init__(self):
self.children = {} # Initialize children as an empty dictionary
self.is_end_of_word = False # Initialize is_end_of_word as False
class Trie:
def __init__(self):
self.root = TrieNode() # Initialize root as a TrieNode
def insert(self, word):
"""Insert a word into the Trie."""
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):
"""Search for a word in the Trie. Return True if found, False otherwise."""
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_prefix(self, prefix):
"""Check if any word in the Trie starts with the given prefix."""
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
def ends_with_suffix(self, suffix):
"""Check if any word in the Trie ends with the given suffix."""
node = self.root
for char in suffix:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def delete(self, word):
"""Delete a word from the Trie."""
def _delete(node, word, index):
if index == len(word):
if not node.is_end_of_word:
return False
node.is_end_of_word = False
return len(node.children) == 0
char = word[index]
if char not in node.children:
return False
should_delete_node = _delete(node.children[char], word, index + 1)
if should_delete_node:
del node.children[char]
return len(node.children) == 0
return False
_delete(self.root, word, 0)
