Ruigu Electronic

        Root (is_end=False)
       /                  \
      c (F)                d (F)
     /                    /
    a (F)                o (T)  → "do"
   / \
  t (T)  r (F)           → "cat"
         \
          t (T)          → "cart"

class TrieNode:
    """Node class for Trie (Prefix Tree)."""
    def __init__(self):
        self.children = {}  # Key: character, Value: TrieNode
        self.is_end = False  # Marks end of a complete string

class Trie:
    def __init__(self):
        self.root = TrieNode()  # Root node (empty character)
    
    # -------------------------- Insert Operation --------------------------
    def insert(self, word: str) -> None:
        """Insert a string into the Trie."""
        current = self.root
        for char in word:
            # Create new node if character not in children
            if char not in current.children:
                current.children[char] = TrieNode()
            # Move to the child node
            current = current.children[char]
        # Mark the end of the word
        current.is_end = True
    
    # -------------------------- Search Operation --------------------------
    def search(self, word: str) -> bool:
        """Check if a complete string exists in the Trie."""
        current = self.root
        for char in word:
            if char not in current.children:
                return False  # Character not found—word doesn't exist
            current = current.children[char]
        # Return True only if the node marks the end of a word
        return current.is_end
    
    # -------------------------- Prefix Search Operation --------------------------
    def starts_with(self, prefix: str) -> bool:
        """Check if any string in the Trie starts with the given prefix."""
        current = self.root
        for char in prefix:
            if char not in current.children:
                return False  # Prefix not found
            current = current.children[char]
        # Prefix exists (no need to check is_end)
        return True
    
    # -------------------------- Autocomplete Operation --------------------------
    def autocomplete(self, prefix: str) -> list:
        """Retrieve all strings in the Trie that start with the given prefix."""
        current = self.root
        # First, traverse to the end of the prefix
        for char in prefix:
            if char not in current.children:
                return []  # Prefix not found—no matches
            current = current.children[char]
        
        # Recursively collect all words starting from the prefix node
        def collect_words(node, current_word, result):
            if node.is_end:
                result.append(current_word)
            # Traverse all children to collect words
            for char, child_node in node.children.items():
                collect_words(child_node, current_word + char, result)
        
        result = []
        collect_words(current, prefix, result)
        return result
    
    # -------------------------- Delete Operation --------------------------
    def delete(self, word: str) -> bool:
        """Delete a string from the Trie. Return True if deleted, False if not found."""
        # Recursive helper to handle deletion (tracks if node can be pruned)
        def _delete_helper(node, word, index) -> bool:
            # Base case: Reached end of word
            if index == len(word):
                # Word not found (node doesn't mark end of word)
                if not node.is_end:
                    return False
                # Unmark end of word
                node.is_end = False
                # Return True if node has no children (can be pruned)
                return len(node.children) == 0
            
            char = word[index]
            # Character not found—word doesn't exist
            if char not in node.children:
                return False
            
            # Recursively delete the next character
            can_prune = _delete_helper(node.children[char], word, index + 1)
            
            # If child can be pruned, remove it from current node's children
            if can_prune:
                del node.children[char]
                # Return True if current node has no children and is not end of another word
                return len(node.children) == 0 and not node.is_end
            
            return False
        
        return _delete_helper(self.root, word, 0)

# Test the Trie implementation
if __name__ == "__main__":
    # Initialize Trie
    trie = Trie()
    
    # Insert words
    words = ["cat", "car", "cart", "dog", "do", "apple", "app"]
    for word in words:
        trie.insert(word)
    
    # Search
    print("=== Search Tests ===")
    print(f"Search 'cat': {trie.search('cat')}")    # Output: True
    print(f"Search 'car': {trie.search('car')}")    # Output: False (not marked as end)
    print(f"Search 'cart': {trie.search('cart')}")  # Output: True
    print(f"Search 'do': {trie.search('do')}")      # Output: True
    print(f"Search 'dog': {trie.search('dog')}")    # Output: True
    print(f"Search 'apple': {trie.search('apple')}")# Output: True
    print(f"Search 'app': {trie.search('app')}")    # Output: True
    print(f"Search 'ap': {trie.search('ap')}")      # Output: False (not end of word)
    
    # Prefix Check
    print("\n=== Prefix Tests ===")
    print(f"Starts with 'ca': {trie.starts_with('ca')}")  # Output: True
    print(f"Starts with 'app': {trie.starts_with('app')}")# Output: True
    print(f"Starts with 'xyz': {trie.starts_with('xyz')}")# Output: False
    
    # Autocomplete
    print("\n=== Autocomplete Tests ===")
    print(f"Autocomplete 'ca': {trie.autocomplete('ca')}")# Output: ['cat', 'cart']
    print(f"Autocomplete 'app': {trie.autocomplete('app')}")# Output: ['app', 'apple']
    print(f"Autocomplete 'd': {trie.autocomplete('d')}")  # Output: ['do', 'dog']
    
    # Delete
    print("\n=== Delete Tests ===")
    trie.delete("cart")
    print(f"After deleting 'cart': Autocomplete 'ca' → {trie.autocomplete('ca')}")# Output: ['cat']
    trie.delete("app")
    print(f"After deleting 'app': Search 'app' → {trie.search('app')}")# Output: False
    print(f"After deleting 'app': Autocomplete 'app' → {trie.autocomplete('app')}")# Output: ['apple']