Implement Trie II (Prefix Tree) - Practice Coding Problems

Implement Trie II (Prefix Tree) - Problem

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.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["Trie", "insert", "insert", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsEqualTo"] arguments = [[], ["apple"], ["app"], ["app"], ["app"], ["app"], ["app"]]

› Output: [null, null, null, 1, 2, null, 0]

💡 Note: Initialize trie, insert "apple" and "app". Count "app": 1 word exactly matches. Count with prefix "app": 2 words ("app" and "apple"). After erasing "app", count becomes 0.

Example 2 — Multiple Insertions

$ Input: operations = ["Trie", "insert", "insert", "insert", "countWordsEqualTo", "countWordsStartingWith"] arguments = [[], ["app"], ["app"], ["apple"], ["app"], ["app"]]

› Output: [null, null, null, null, 2, 3]

💡 Note: After inserting "app" twice and "apple" once: exactly 2 instances of "app", and 3 total words starting with "app" prefix.

Example 3 — Empty Prefix Search

$ Input: operations = ["Trie", "insert", "countWordsStartingWith", "countWordsEqualTo"] arguments = [[], ["hello"], [""], [""]]

› Output: [null, null, 1, 0]

💡 Note: Empty prefix matches all words (1 word total). Empty string as exact word match returns 0 since we didn't insert empty string.

Constraints

1 ≤ word.length, prefix.length ≤ 2000
word and prefix consist only of lowercase English letters
At most 3 × 10⁴ calls 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

Visualization

Tap to expand

Understanding the Visualization

Input

Sequence of operations: insert, count, erase

Process

Build tree structure with character nodes

Output

Return counts based on tree traversal

Key Takeaway

🎯 Key Insight: Store strings as tree paths where each node tracks word endings and prefix counts for O(m) operations

Asked in

G Google 45 a Amazon 38 M Microsoft 32 F Facebook 28

The key insight is to use a tree where each node represents a character and stores counts for words ending at that node and prefixes passing through it. Best approach is the optimized trie with O(m) time per operation and O(n×m) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - List Storage	O(n×m)	O(n×m)	Store all words in a list and iterate through for each operation
Optimized Trie Implementation	O(m)	O(n×m)	Use a tree structure where each node represents a character

Brute Force - List Storage — Algorithm Steps

Store all words in a list
For queries, iterate through entire list
Count matches based on exact equality or prefix matching

Visualization

Tap to expand

Step-by-Step Walkthrough

Insert

Add word to end of list

Iterate through entire list

Count

Count matching words

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_WORDS 1000
#define MAX_WORD_LEN 100

typedef struct {
    char words[MAX_WORDS][MAX_WORD_LEN];
    int count;
} Trie;

Trie* trieCreate() {
    Trie* trie = (Trie*)malloc(sizeof(Trie));
    trie->count = 0;
    return trie;
}

void trieInsert(Trie* obj, char* word) {
    strcpy(obj->words[obj->count], word);
    obj->count++;
}

int trieCountWordsEqualTo(Trie* obj, char* word) {
    int count = 0;
    for (int i = 0; i < obj->count; i++) {
        if (strcmp(obj->words[i], word) == 0) {
            count++;
        }
    }
    return count;
}

int trieCountWordsStartingWith(Trie* obj, char* prefix) {
    int count = 0;
    int prefixLen = strlen(prefix);
    for (int i = 0; i < obj->count; i++) {
        if (strncmp(obj->words[i], prefix, prefixLen) == 0) {
            count++;
        }
    }
    return count;
}

void trieErase(Trie* obj, char* word) {
    for (int i = 0; i < obj->count; i++) {
        if (strcmp(obj->words[i], word) == 0) {
            for (int j = i; j < obj->count - 1; j++) {
                strcpy(obj->words[j], obj->words[j + 1]);
            }
            obj->count--;
            break;
        }
    }
}

int main() {
    printf("[null,null,null,1,1,null,0]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

For each operation, we may need to check all n words, each of length m

✓ Linear Growth

Space Complexity

O(n×m)

Store all n words, each of average length m

⚡ Linearithmic Space

23.5K Views

High Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - List Storage — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler