Implement a Prefix-Based Word Store

Brute Force — Keep Every Word and Scan for Prefixes Exact word lookup is straightforward: a hash set answers search in average constant time. The harder operation is startsWith, because it asks about a prefix rather than a complete word. Precomputing every prefix would work, but a simple fallback is to keep all inserted words in a list and check each one when a prefix query arrives. Suppose we insert bat, then batch. search("bat") is true because bat was inserted exactly.…