How do you approach Implement Trie?

Use a tree structure where each node has children for each letter.

What is the time complexity of Implement Trie?

Time complexity: O(m) per operation where m is the word/prefix length. Space complexity: O(total characters inserted).

What are common mistakes on Implement Trie?

Leaving out the end-of-word flag, so a lookup reports words that were never inserted. Allocating a fixed 26-child array per node for a sparse alphabet, when a map keeps the memory honest. Not handling the empty string, which is a valid prefix of everything.

gitGood.dev

← Back to problems

Implement Trie

MediumData Structures

Description

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

insert(word) inserts the string word into the trie.
search(word) returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
startsWith(prefix) returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Note: For this problem, implement operations as a function that takes a list of commands and returns the results. Return null for void operations (insert).

Example 1

Input: operations = [["insert","apple"],["search","apple"],["search","app"],["startsWith","app"],["insert","app"],["search","app"]]

Output: [null,true,false,true,null,true]

Constraints

- 1 <= word.length, prefix.length <= 2000 - word and prefix consist only of lowercase English letters. - At most 3 * 10^4 total calls will be made to insert, search, and startsWith.

Implement Trie: approach, complexity and pitfalls

A medium trie problem, graded against 6 test cases (3 of them hidden).

The pattern: Trie

A prefix tree for fast string lookup by shared prefix.

Reach for it when you see: Many words, repeated prefix queries, autocomplete, or word-search over a grid.

If you are stuck

Show the 3-step hint ladder

Use a tree structure where each node has children for each letter.
Each node needs a flag to indicate if it marks the end of a word.
For startsWith, you only need to verify the path exists - no need to check the end flag.

The optimal approach

Show the approach: Trie with Hash Map Children

Each node stores a map of children (letter -> node) and an end-of-word flag. Insert creates nodes as needed. Search follows the path and checks the end flag. StartsWith follows the path without checking the end flag.

Time: O(m) per operation where m is the word/prefix length
Space: O(total characters inserted)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Trie mistakes

These apply to the pattern as a whole, not just this problem.

Leaving out the end-of-word flag, so a lookup reports words that were never inserted.
Allocating a fixed 26-child array per node for a sparse alphabet, when a map keeps the memory honest.
Not handling the empty string, which is a valid prefix of everything.