DSA Factory
Free lessonsTries · Stage 0 · Words as paths · Step 2

Starts with

Walk a prefix through the trie without checking any end marker: reaching the last letter is enough. About 8 minutes.

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"
•dogorcat

"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.
Quick check

words = ["dog", "door"]. Does anything start with "do"?

  1. AYes
  2. BNo, because "do" isn't itself a word
Show the answer

Yes. The path d → o exists, and both words extend it.

Your problem

Starts with

words is a list of lowercase words. Return true if any word in words starts with prefix, or false otherwise.

Example
words = ["dog", "door", "cat"], prefix = "do" → true

0 ≤ words.length ≤ 1,000 · 1 ≤ words[i].length, prefix.length ≤ 30 · every word is lowercase a-z

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding