Build a Prefix Tree | Practice

Write a class Trie (a prefix tree) that stores lowercase words:

Trie() makes an empty trie.
insert(word) stores word.
search(word) returns true if word has been stored, and false otherwise.
startsWith(prefix) returns true if some stored word begins with prefix, and false otherwise. A word counts as beginning with itself.

Each test is a list of calls, starting with the constructor; the expected answer lists what each call returns (null for the constructor and for insert).

Example 1

Calls: Trie(), insert("card"), search("car"), startsWith("car"), insert("car"), search("car")
Returns: [null, null, false, true, null, true]

Until "car" is inserted, it is only the start of "card", not a stored word.

Example 2

Calls: Trie(), insert("on"), insert("one"), startsWith("onex"), search("one"), search("o")
Returns: [null, null, null, false, true, false]

Constraints

Words and prefixes have 1 to 2000 lowercase English letters.
A test makes at most 3 × 10⁴ calls.

Show the pattern

Trie

Words that start the same way should share the work. A tree with one edge per letter stores each shared start once, and every lookup walks it in time proportional to the word's length.

See trie in a visualiser

Show the approach

Each node holds a map from a letter to a child node, and a flag end saying whether a stored word ends there. The root stands for the empty start.

insert: walk down from the root letter by letter, making any missing child, then set end on the node you finish on.
search and startsWith: walk down the same way, and give up as soon as a letter's child is missing. If the walk finishes, startsWith answers true, while search answers the last node's end flag.

Time: O(L) per call, for a word of length L · Space: O(total letters stored)

Brush up firstTrie (Prefix Matching) visualiser