Practice Problem

Implement Trie (Prefix Tree)

Difficulty: Medium

Implement a trie (prefix tree) that supports inserting words, searching for exact words, and checking if any word starts with a given prefix.

Implement Trie (Prefix Tree)

A trie (pronounced "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Common applications include autocomplete systems and spell checkers.

Implement the Trie class:

Trie(): Initializes the trie object.
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.

Examples

Example 1:

Input:
  Trie(), insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")
Output:
  null, null, true, false, true, null, true
Explanation:
  trie = new Trie();
  trie.insert("apple");       // Inserts "apple" into the trie
  trie.search("apple");       // Returns true
  trie.search("app");         // Returns false ("app" was not inserted)
  trie.startsWith("app");     // Returns true ("apple" starts with "app")
  trie.insert("app");         // Inserts "app" into the trie
  trie.search("app");         // Returns true ("app" is now in the trie)

Example 2:

Input:
  Trie(), insert("banana"), insert("band"), search("ban"), startsWith("ban"), search("band")
Output:
  null, null, null, false, true, true
Explanation:
  trie = new Trie();
  trie.insert("banana");      // Inserts "banana"
  trie.insert("band");        // Inserts "band"
  trie.search("ban");         // Returns false ("ban" not inserted)
  trie.startsWith("ban");     // Returns true ("banana" and "band" start with "ban")
  trie.search("band");        // Returns true

Constraints

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

Expected Complexity

Time: O(m) per operation, where m is the length of the word or prefix
Space: O(T) where T is the total number of characters across all inserted words (worst case, no shared prefixes)

MEDIUM

Trie / Prefix Tree

Trie Operations

Design Patterns

Strings

Intermediate

0 views

Solution

JavaScript

Python

Hints

Hint 1

Hint 2

Premium

Hint 3

Premium

Hint 4

Premium

Solution Walkthrough and Reference Code

Premium

All Problems