LeetCode 208 · Medium · Tries

Implement Trie (Prefix Tree)

Build a trie with three operations: insert(word) stores a word, search(word) says whether that exact word was stored, and startsWith(prefix) says whether any stored word begins with the prefix.

O(L)per call · L = word length
O(total letters)space
trieone node per shared prefix

insert w, search w, startsWith p, separated by ; · 1 to 10 calls · words a–z, 1 to 6 letters

Calls → return value · yellow = running

word c = the letter being followed

c
class TrieNode { Map<Character, TrieNode> children = new HashMap<>(); boolean endOfWord = false;}class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { TrieNode cur = root; for (char c : word.toCharArray()) { if (!cur.children.containsKey(c)) { cur.children.put(c, new TrieNode()); } cur = cur.children.get(c); } cur.endOfWord = true; } public boolean search(String word) { TrieNode cur = root; for (char c : word.toCharArray()) { if (!cur.children.containsKey(c)) { return false; } cur = cur.children.get(c); } return cur.endOfWord; } public boolean startsWith(String prefix) { TrieNode cur = root; for (char c : prefix.toCharArray()) { if (!cur.children.containsKey(c)) { return false; } cur = cur.children.get(c); } return true; }}
call
—
c
—
cur
—
return
—
nodes
1

Why it works

  1. Brute force keeps a list of words and scans all of them: search compares every word, startsWith checks every word's beginning. O(n·L) per call for n stored words.
  2. Words that share a prefix share a path. Each node is one prefix; its children are the letters that can follow it. So a call never looks at other words, only at its own letters, one edge per letter. endOfWord marks the nodes where a whole word stops (the double rings).
  3. Every call walks at most L edges with an O(1) hash map lookup each: O(L) time, no matter how many words are stored. Space is one node per distinct prefix, at most the total number of letters inserted.
  4. Pitfall: treating "the path exists" as "the word exists". After insert apple, the path for app exists, yet search app is false until app is inserted; only startsWith ignores the end mark.
  5. Next: Design Add and Search Words (211) adds a . wildcard that branches into every child; Word Search II (212) walks a trie and a letter board together.