Trie vs Hash Set

Both store strings.

When to use each? Use hash set when:

• Only need exact lookups (contains/add/remove)
• Prefix queries not needed
• Memory is limited

Use trie when:

• Need prefix queries (startsWith, autocomplete)
• Need to find all words with a prefix
• Lexicographic ordering matters
• Pattern matching with wildcards

Hash set lookup is $O(L)$ average (hash computation), but $O(L \cdot n)$ worst case with collisions.

Trie is always $O(L)$. For most string lookup problems without prefix requirements, hash sets are simpler. Add prefix queries, and tries become needed.