Prefix Search and StartsWith Operations
What you'll learn: How to check whether any stored word begins with a given prefix by partially traversing a trie.
The Core Idea
Once you've inserted words into a trie, you can efficiently answer "Does any word I've stored start with these letters?" without checking every full word. Instead, you walk down the trie following the prefix letters. If you can successfully traverse all the prefix characters without hitting a dead-end, at least one word starts with that prefix.
Think of it like this: if you're looking up names in a phone book and want to find anyone whose name starts with "Mar," you only need to flip to the M section, then Ma, then Mar — you don't need to read complete names. If that section exists, you've found matches.
How It Works
To implement startsWith(prefix):
- Start at the root of your trie
- For each character in the prefix:
- Check if a child node exists for that character
- If not, return
false(no word starts with this prefix) - If yes, move to that child node
- If you successfully traverse all characters, return
true
Notice the difference from exact search: you don't check for an "end of word" marker. You only care whether the path exists, not whether it marks a complete word.
Example
If your trie contains ["apple", "app", "application"]:
startsWith("app")→true(all three words match)startsWith("appl")→true(two words match)startsWith("orange")→false(no matching path)
Key Takeaway: Prefix search traverses only as deep as the prefix length, returning true if the path exists—regardless of whether it marks a complete word—making autocomplete and search suggestions extremely efficient.