-
Notifications
You must be signed in to change notification settings - Fork 0
091 — Implement Trie Prefix Tree
LeetCode 208 · Medium. Design a trie with insert(word), search(word) (exact match), and startsWith(prefix) (prefix match) — all three operations should be efficient regardless of how many words are already stored.
This one is refreshingly literal: it's not "find the trie pattern hiding inside a harder problem," it's "please build the data structure itself." Picture a filing cabinet organized one letter at a time — drawer c, inside it a folder a, inside that a folder t with a little flag on it saying "yes, 'cat' is a real word here." To store "car" too, you reuse the c drawer and the a folder — you only need a new folder for r. That reuse of shared prefixes is the entire idea: instead of storing each word as its own independent blob (like a Set<String> would), you store paths, and words that start the same way share the same path for as long as they agree.
"Implement a data structure that supports insert / search / prefix-search" — the explicit mention of prefix search alongside exact search is the tell. If a problem only needed exact membership, a hash set would do; the moment "starts with" enters the requirements, you need a structure that makes shared prefixes a first-class, walkable path, which is exactly what a trie is built for.
Store every inserted word in an array (or set), and answer search with an exact-match scan and startsWith with a scan checking hasPrefix on every stored word.
class TrieBruteForce {
private var words: [String] = []
func insert(_ word: String) {
words.append(word)
}
func search(_ word: String) -> Bool {
for w in words where w == word {
return true
}
return false
}
func startsWith(_ prefix: String) -> Bool {
for w in words where w.hasPrefix(prefix) {
return true
}
return false
}
}
// smoke test
let bf = TrieBruteForce()
bf.insert("apple")
print(bf.search("apple")) // true
print(bf.search("app")) // false — "app" was never inserted
print(bf.startsWith("app")) // true — "apple" starts with "app"Big-O: insert is O(m) (appending, m = word length, amortized). search and startsWith are O(n · m) each — in the worst case every one of the n stored words must be compared/scanned character by character. Space is O(total characters stored).
Build an actual trie: a TrieNode with a children dictionary keyed by character and an isEndOfWord flag, plus a root. insert walks/creates one node per character; search and startsWith walk the same path and differ only in whether they check the end-of-word flag at the finish line.
final class TrieNode {
var children: [Character: TrieNode] = [:]
var isEndOfWord = false
}
final class Trie {
private let root = TrieNode()
func insert(_ word: String) {
var node = root
for char in word {
if let next = node.children[char] {
node = next
} else {
let next = TrieNode()
node.children[char] = next
node = next
}
}
node.isEndOfWord = true
}
func search(_ word: String) -> Bool {
guard let node = walk(word) else { return false }
return node.isEndOfWord
}
func startsWith(_ prefix: String) -> Bool {
walk(prefix) != nil
}
private func walk(_ text: String) -> TrieNode? {
var node = root
for char in text {
guard let next = node.children[char] else { return nil }
node = next
}
return node
}
}
// smoke test
let trie = Trie()
trie.insert("apple")
print(trie.search("apple")) // true — inserted exactly, end-of-word reached
print(trie.search("app")) // false — path exists but isEndOfWord is false at that node
print(trie.startsWith("app")) // true — the path a -> p -> p exists
trie.insert("app")
print(trie.search("app")) // true — now "app" was explicitly inserted, flag flips to trueBig-O: insert, search, and startsWith are all O(m), where m is the length of the word/prefix — completely independent of n, the number of words already stored. Space is O(total characters across all inserted words), with shared prefixes stored once.
The brute force treats every stored word as an opaque, independent string — answering "does any word start with this prefix" forces you to re-scan and re-compare every single stored word from scratch, so the cost grows with n (how many words you've stored) as well as m (how long the query is). The optimal trie flips the storage itself: instead of storing whole words side by side, it stores shared paths through a tree, so "does any word start with this prefix" becomes "can I walk this exact path from the root" — a question answered in O(m), with n never entering the cost at all. Nothing about the algorithm gets cleverer; the data layout just stops duplicating the prefixes that queries actually care about.
-
Tries — this chapter is that data structure; everything here is the foundational
TrieNode/Trieshape put directly into practice, not a distinct algorithmic pattern layered on top of it. -
DFS and Backtracking —
insert,search, andstartsWithare all a recursive descent through children in disguise (written iteratively here, but the same one-step-at-a-time walk down a branching structure that backtracking search relies on).
A trie is a filing cabinet built one letter at a time — shared prefixes share drawers, and a flag (not a whole separate word) marks where a real entry actually ends.
Insert "apple", "app", and "apply" into an empty trie, in that order. Draw (or describe) which nodes get created versus reused at each step, and identify every node along the way that ends up with isEndOfWord == true. Then explain: why does search("app") need to check isEndOfWord at all, instead of simply returning true whenever walk successfully reaches a node?
⬅️ Previous: Serialize and Deserialize Binary Tree · Next: Design Add and Search Words Data Structure ➡️