The problem
Implement a Trie (prefix tree) with insert(word), search(word) (is that exact word stored?) and startsWith(prefix) (does any stored word start with it?).
Input: insert apple, search apple, search app, startsWith app, insert app, search app Output: true, false, true, true
Picture it
Picture a letter tree. Each step down a branch is one letter, so words that start the same way share the same branch (“app” and “apple” share a-p-p). A node gets a special end mark when a whole word finishes there. Searching just walks down the letters; if a letter branch is missing, the word isn’t there.
How to recognise it
- You store many strings and must answer prefix questions: "does any word start with this?", "list the words that start with this", autocomplete.
- Words share beginnings (
app,apple,apply), so storing each shared beginning once saves both space and work. - Each query should cost time proportional to the length of the query, not the number of stored words.
- A trie (prefix tree) is a tree where each edge is one letter and each path from the root spells a prefix. A marker on a node says "a whole word ends here".
Start with brute force
Keep the words in a set. Exact search is a set lookup; a prefix query checks every stored word.
class TrieBrute:
def __init__(self):
self.words = set()
def insert(self, word):
self.words.add(word)
def search(self, word):
return word in self.words
def starts_with(self, prefix):
return any(w.startswith(prefix) for w in self.words)
insert and search are O(L) for a word of length L (hashing reads every character). But starts_with is O(N · L) for N stored words. LeetCode allows 3 × 10^4 calls: 1.5 × 10^4 inserts followed by 1.5 × 10^4 prefix queries that miss is about 2.25 × 10^8 startswith checks.
From brute force to the idea
- Find the waste. A prefix query compares the prefix with every word, even words that differ in the first letter. And
app,appleandapplyeach store the sameappagain. - Share prefixes. Build a tree of nested dictionaries:
self.rootmaps a first letter to a child dictionary, which maps the next letter to its child, and so on. - Insert by walking and growing. For each letter,
node.setdefault(ch, {})follows the branch if it exists and creates it otherwise. At the end,node["$"] = Truemarks that a word ends here. The$key cannot clash with a letter because words use only lowercase letters. - Search by walking. Follow one letter at a time. A missing letter means no stored word has this prefix, so return
False. - One walk, two questions. After the walk, a prefix query is already satisfied (
prefix or ...). An exact search also needs the$marker, becauseappcan be a path insideapplewithout being a stored word.starts_withsimply callssearch(prefix, prefix=True).
This is the key idea: follow the query one letter at a time down shared branches; the end node tells you whether it is a prefix, and its marker whether it is a word.
The key idea
Each node holds children by letter plus an end-of-word flag. Every operation costs O(length of the word).
Python solution
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {}) # grow a branch if missing
node["$"] = True # mark: a word ends here
def search(self, word, prefix=False):
node = self.root
for ch in word:
if ch not in node:
return False
node = node[ch]
return prefix or "$" in node
def starts_with(self, prefix):
return self.search(prefix, prefix=True)In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | insert and search O(L); starts_with O(N · L): every word is checked | O(total characters) |
| Dictionary trie (shown code) | O(L) for every operation: one dictionary step per letter | O(total characters) in the worst case, less when prefixes are shared; each node is a whole dictionary, so the constant is large |
Edge cases
- The example: after inserting
apple,search("app")isFalseandstarts_with("app")isTrue; after insertingapp,search("app")isTrue. - Inserting a word twice: harmless; the path exists and the marker is set again.
- Query longer than any word (
search("apples")): the walk hits a missingsand returnsFalse. - Empty prefix:
starts_with("")returnsTrueeven on an empty trie, because the walk does nothing. Whether that is right depends on your definition; LeetCode never asks it. - Empty word:
search("")isFalseunless""was inserted, which marks the root.
Common mistakes
- Forgetting the end marker and answering
searchwith "did the walk succeed?". Thensearch("app")isTrueafter inserting onlyapple. - Creating nodes during
search(usingsetdefaultthere), which makes the trie grow on every miss. - Using a letter as the marker key or storing the marker as a child, so a word containing that character breaks.
- Storing the whole word at every node "to make autocomplete easy", which turns the space cost from shared prefixes into O(L²) per word.
Add count_prefix(prefix): how many inserted words start with the prefix (a word inserted twice counts twice). After inserting apple, app, apply, bat and apple again, count_prefix("app") is 4. Each call must stay O(L). Describe your approach, then write it if you like.
Compare with our answer
Store a counter in every node: how many inserted words passed through it. Increment along the path on each insert. A query walks to the prefix's node and reads its counter, so no subtree is explored.
class CountTrie:
def __init__(self):
self.root = {"#": 0}
def insert(self, word):
node = self.root
node["#"] += 1
for ch in word:
node = node.setdefault(ch, {"#": 0})
node["#"] += 1 # one more word passes through here
def count_prefix(self, prefix):
node = self.root
for ch in prefix:
if ch not in node:
return 0
node = node[ch]
return node["#"]
count_prefix("") is the total number of inserts. Both methods are O(L).
A strong answer mentions: updating the counter on every node of the path (including the root), why a missing letter returns 0, and why this beats walking the whole subtree.
1. A search box must suggest stored product names that begin with what the user has typed so far. Which structure fits best?
The trie reaches the typed prefix in O(L) and the matching names all sit below that node. Checking every name is O(N · L) per keystroke, and storing every prefix of every name costs far more memory.
2. Why does search("app") return False after inserting only apple?
The path a, p, p exists because it is part of apple, so only the marker can tell the two apart. The marker is set only where an inserted word ends.
3. A learner rewrites the last line of search as return "$" in node. After inserting apple, which call now gives a wrong answer?
starts_with relies on prefix or to accept a path with no marker, so it now returns False for app. The exact searches still check the marker, and b fails during the walk either way.
Score 60% or more and the lesson is marked complete.