Smart Search Autocomplete Engine

class TrieNode:
  """A single node in the Prefix Tree representing a single character."""
  def __init__(self):
      # A dictionary to store child nodes. Key: character, Value: TrieNode
      self.children = {}
      # Marks if this specific node represents the end of a valid dictionary word
      self.is_end_of_word = False

class AutocompleteSystem:
  """The main system that manages the Trie data structure and algorithms."""
  def __init__(self):
      # The root of the tree is always an empty node
      self.root = TrieNode()

  def insert_word(self, word):
      """DSA Concept: Inserting data into a Tree."""
      current_node = self.root
      
      # Traverse letter by letter
      for char in word.lower():
          # If the letter doesn't exist as a branch, create it
          if char not in current_node.children:
              current_node.children[char] = TrieNode()
          # Move down to the next node
          current_node = current_node.children[char]
          
      # We reached the end of the word, mark it as valid
      current_node.is_end_of_word = True

  def _dfs(self, node, current_prefix, suggestions):
      """
      DSA Concept: Depth-First Search (DFS) Algorithm.
      Recursively travels down the branches to find complete words.
      """
      # If the current node is a valid word, add it to our list
      if node.is_end_of_word:
          suggestions.append(current_prefix)
          
      # Explore all children of this node
      for char, child_node in node.children.items():
          self._dfs(child_node, current_prefix + char, suggestions)

  def get_suggestions(self, prefix):
      """Searches the Trie for a given prefix and triggers the DFS."""
      prefix = prefix.lower()
      current_node = self.root
      
      # Step 1: Navigate to the end of the user's prefix
      for char in prefix:
          if char not in current_node.children:
              # The prefix doesn't exist in our dictionary at all
              return [] 
          current_node = current_node.children[char]
          
      # Step 2: We found the prefix. Now use DFS to find all words branching from here
      suggestions = []
      self._dfs(current_node, prefix, suggestions)
      
      return suggestions

# --- Execution & User Interface ---
if __name__ == "__main__":
  print("⚙️ Booting up Autocomplete Engine...")
  engine = AutocompleteSystem()
  
  # 1. Create a dummy database of words
  database = [
      "python", "pycharm", "pypi", "programming", "program", 
      "project", "algorithm", "algo", "alien", "apple", "app",
      "data", "database", "structure", "software"
  ]
  
  print("📚 Loading dictionary into the Trie...")
  for word in database:
      engine.insert_word(word)
      
  print("
✅ System Ready!")
  print("Type a few letters to get suggestions (or type 'exit' to quit).")
  
  # 2. Interactive Loop
  while True:
      print("-" * 40)
      user_input = input("🔍 Search: ")
      
      if user_input.lower() == 'exit':
          print("Shutting down engine. Goodbye!")
          break
          
      if not user_input.strip():
          continue
          
      # Get suggestions using our DSA engine
      results = engine.get_suggestions(user_input)
      
      if results:
          print(f"💡 Suggestions: {', '.join(results)}")
      else:
          print("🚫 No suggestions found.")