Almost the same walk

This is the same letter-by-letter walk as checking for an exact word, with one change: there is no end-marker check at the finish. If every letter of the prefix was found, some inserted word must continue along that path, because nodes are only ever created while inserting a real word.

It is like following signposts: if the road exists, it leads to some town.

Reused walk: same missing-letter check as searching for a whole word.

No end check: the prefix itself doesn't need to be a complete word.

In code

root = {}
for w in words:
    node = root
    for c in w:
        node = node.setdefault(c, {})
node = root
for c in prefix:
    if c not in node:
        return False
    node = node[c]
return True

words = [dog, door, cat], prefix = "do"

"dog" and "door" share the path d → o, so the trie stores it once. The grouping by beginnings is already done.

Move 1 of 4

A hash set can't do this in one step

Asking "does any word start with ca?" of a hash set means scanning every word and comparing its first two letters: one check per word, like flipping through every page of a phone book.

A trie already grouped the words by their beginnings when it was built, so the answer is just: does that path exist?

Built once: the grouping work happens during insert, not during every search.