Trie vs Hash Set

The Idea

A hash set turns a word into a bucket. That is unbeatable for "is this exact word stored?" and it costs less memory than a node per character.

The moment the question involves a prefix, hashing has thrown away what you need. A trie keeps it. Pick by the question you will actually ask.

Real-World Example

A router matching a destination address picks the longest stored prefix that fits — a trie job. The same router's blocklist of exact addresses is a hash set, because nothing about "close to" matters there.

The Code

words = {"car", "cart", "cat", "dog"}
print("cart" in words)                                   # exact hit, O(1)
print(sorted(w for w in words if w.startswith("ca")))    # O(n): scans everything

trie = {"c": {"a": {"r": {"$": 1, "t": {"$": 1}}, "t": {"$": 1}}}}
node = trie
for ch in "ca":                       # O(len(prefix)), then read the subtree
    node = node[ch]
print(sorted(node))                   # only the 'ca' branch was touched

words = {"ate", "atom", "be"}
trie = {"a": {"t": {"e": {"$": 1}, "o": {"m": {"$": 1}}}}, "b": {"e": {"$": 1}}}
print(len(words), len(trie))