Implement Trie (Prefix Tree)

Medium#208insert and search

Build a class with three methods: insert(word) adds a word, search(word) says whether exactly this word was added, and startsWith(prefix) says whether some added word begins with these letters. Our calls: insert("top"), insert("tea"), search("to"), startsWith("to"), insert("to"), search("to"), startsWith("tu") — they return false, true, true and false; the inserts return nothing.

208 Implement Trie (Prefix Tree)Walkthrough · 1×

Example: insert("top"), insert("tea"), search("to"), startsWith("to"), insert("to"), search("to"), startsWith("tu"). Answers are listed under the word being walked.

root
in the trie; a double ring ends a wordjust addedthe path so farcurrent nodethe call returns truemissing letter

Trie() is created: the trie is only its root

01/75
restart · back · play · step
Speed
1class Trie:
2 function init():
3 root = new node
4 function insert(word):
5 node = root
6 for each ch in word:
7 if ch not in node.children:
8 node.children[ch] = new node
9 node = node.children[ch]
10 node.end = true
11 function search(word):
12 node = find(word)
13 return node is not none and node.end
14 function startsWith(prefix):
15 return find(prefix) is not none
16 function find(word):
17 node = root
18 for each ch in word:
19 if ch not in node.children:
20 return none
21 node = node.children[ch]
22 return node
state
word
–
prefix
–
ch
–
node
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A word is stored as a path of letters from the root, so every word that starts with the same letters walks through the same nodes, and find reaches the node for any prefix in as many steps as the prefix has letters.
  2. Reaching the node only proves that some word starts this way. A whole word needs its own end mark: that is the one difference between search and startsWith.
  3. A word that is the start of a longer one, like "to" in "top", already has its path. Inserting it adds no node and only sets the mark.

Complexity

Time O(L) per call, where L is the length of its word: one step per letter. Memory O(total letters of the inserted words): at most one node per letter, fewer when words share a start.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.