Skip to main content
Talentd

Implement Trie II (Prefix Tree) - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableStringDesignTrie14 min readAsked at: Amazon, Microsoft
Practice this problem

Problem Statement

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:

  • Trie() Initializes the trie object.
  • void insert(String word) Inserts the string word into the trie.
  • int countWordsEqualTo(String word) Returns the number of instances of the string word in the trie.
  • int countWordsStartingWith(String prefix) Returns the number of strings in the trie that have the string prefix as a prefix.
  • void erase(String word) Erases the string word from the trie.

 

Example 1:

Input
["Trie", "insert", "insert", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsStartingWith"]
[[], ["apple"], ["apple"], ["apple"], ["app"], ["apple"], ["apple"], ["app"], ["apple"], ["app"]]
Output
[null, null, null, 2, 2, null, 1, 1, null, 0]

Explanation
Trie trie = new Trie();
trie.insert("apple");               // Inserts "apple".
trie.insert("apple");               // Inserts another "apple".
trie.countWordsEqualTo("apple");    // There are two instances of "apple" so return 2.
trie.countWordsStartingWith("app"); // "app" is a prefix of "apple" so return 2.
trie.erase("apple");                // Erases one "apple".
trie.countWordsEqualTo("apple");    // Now there is only one instance of "apple" so return 1.
trie.countWordsStartingWith("app"); // return 1
trie.erase("apple");                // Erases "apple". Now the trie is empty.
trie.countWordsStartingWith("app"); // return 0

 

Constraints:

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most 3 * 104 calls in total will be made to insert, countWordsEqualTo, countWordsStartingWith, and erase.
  • It is guaranteed that for any function call to erase, the string word will exist in the trie.

Approach Overview

Problem Overview: Design a Trie (prefix tree) that supports insert, countWordsEqualTo, countWordsStartingWith, and erase. Unlike the basic Trie problem, you must track how many times a word or prefix appears.

Approach 1: Store All Words in Hash Map (Brute Force) (Time: O(N * L), Space: O(N * L))

Keep a hash map where keys are full words and values store their frequency. insert increments the count, and countWordsEqualTo becomes a direct hash lookup. For countWordsStartingWith, iterate through every stored word and check if it starts with the prefix using string comparison. This approach is easy to implement but inefficient when many words exist because each prefix query scans the entire dataset. Useful only for small inputs or quick prototypes involving hash tables and strings.

Approach 2: Trie with HashMap Children (Time: O(L) per operation, Space: O(N * L))

Build a standard Trie where each node stores children in a hash map keyed by character. Each node maintains two counters: how many words pass through the node (prefixCount) and how many end at the node (endCount). During insert, traverse character by character, creating nodes if needed and updating counters. Prefix queries follow the path of the prefix and return prefixCount. This avoids scanning all words and makes operations proportional only to the word length.

Approach 3: Trie with Fixed Array (Optimal) (Time: O(L) per operation, Space: O(26 * nodes))

Instead of a hash map, each Trie node stores a fixed array of size 26 for lowercase English letters. Character transitions use index = c - 'a', giving constant-time child access. Maintain two counters per node: prefixCount (how many words pass through) and endCount (how many words end here). insert increments both counters appropriately, countWordsEqualTo reads endCount, countWordsStartingWith reads prefixCount, and erase decrements counts while traversing the path. Array indexing is faster and more memory predictable than hash maps, making this the preferred design solution.

Recommended for interviews: The array-based Trie is the expected solution. It demonstrates understanding of Trie structure, prefix counting, and efficient character indexing. Mentioning the brute-force hash map approach shows baseline reasoning, but implementing the Trie with counters proves you can design scalable string data structures.

Solution

Each node in the Trie includes three parts:

  1. An array of pointers children pointing to child nodes. For this problem, the array length is 26, which is the number of lowercase English letters. children[0] corresponds to the lowercase letter a, ..., children[25] corresponds to the lowercase letter z.
  2. An int variable v, representing the number of strings ending with this node.
  3. An int variable pv, representing the number of strings with this node as the prefix node.

1. Insert String

We start from the root of the Trie and insert the string. For the child node corresponding to the current character, there are two cases:

  • The child node exists. Move to the child node along the pointer and continue to process the next character.
  • The child node does not exist. Create a new child node, record it in the corresponding position of the children array, then move to the child node along the pointer, and increase the pv value of the child node by 1. Continue to search for the next character.

Repeat the above steps until the last character of the string is processed, then increase the v value of the current node by 1.

The time complexity is O(n), where n is the length of the string.

2. Search Prefix

We start from the root of the Trie and search for the prefix. For the child node corresponding to the current character, there are two cases:

  • The child node exists. Move to the child node along the pointer and continue to search for the next character.
  • The child node does not exist. This means that the Trie does not contain this prefix, return a null pointer.

Repeat the above steps until a null pointer is returned or the last character of the prefix is searched.

The time complexity is O(n), where n is the length of the string.

3. Remove String

We start from the root node of the Trie, and sequentially reduce the pv value of the corresponding child node by 1, until the last character of the string is searched. Then reduce the v value of the current node by 1.

The time complexity is O(n), where n is the length of the string.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map of Words (Brute Force)O(N * L)O(N * L)Small datasets or quick prototype without building a Trie
Trie with HashMap ChildrenO(L)O(N * L)Flexible character sets or when alphabet size is large
Trie with Fixed ArrayO(L)O(26 * nodes)Interview standard for lowercase strings; fastest lookups

Video Solution

LeetCode 1804. Implement Trie II (Prefix Tree) | Locked Question • 宰相小甘罗 • 465 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Implement Trie II (Prefix Tree) easy or hard?
Implement Trie II (Prefix Tree) is rated Medium. The main challenge is correctly maintaining prefix and word counters while supporting insert and erase operations. Understanding Trie traversal and node bookkeeping makes the problem straightforward.
Implement Trie II (Prefix Tree) Python/Java solution
The standard solution builds a Trie class with nodes containing a 26-length array for lowercase letters and two counters: prefixCount and endCount. Insert updates counts while traversing characters. Query methods simply follow the prefix path and return stored counters.
How to solve Implement Trie II (Prefix Tree) in O(n)?
Each operation can be implemented in O(L) time using a Trie, where L is the word length. Traverse the Trie character by character using array indexing or a hash map. Maintain prefix and end counters at each node to support fast counting queries and deletions.
What is the best approach for Implement Trie II (Prefix Tree)?
The best approach uses a Trie with fixed-size arrays for children and counters at each node. Each node stores prefixCount (words passing through) and endCount (words ending at the node). All operations—insert, countWordsEqualTo, countWordsStartingWith, and erase—run in O(L) time where L is the word length. This approach is both fast and commonly expected in interviews.
Is Implement Trie II (Prefix Tree) asked at Google/Amazon/Meta?
Trie design problems frequently appear in interviews at companies like Google, Amazon, and Meta, especially for roles involving search systems, autocomplete, or text processing. Variants of prefix trees and word dictionaries are common interview patterns.
What data structure is used in Implement Trie II (Prefix Tree)?
The core data structure is a Trie (prefix tree). Each node represents a character and links to child nodes representing the next characters. Additional counters track how many words share a prefix and how many end at a node.
What is the time complexity of Implement Trie II (Prefix Tree)?
Trie operations run in O(L) time, where L is the length of the word or prefix. Each character leads to a single node traversal in the Trie. Space complexity is O(N * L) in the worst case for storing all inserted words in the structure.

Ready to solve this problem?

Practice Implement Trie II (Prefix Tree) with our built-in code editor and test cases.

Practice on FleetCode
Previous

Encrypt and Decrypt Strings

Next

Implement Trie (Prefix Tree)