Implement Trie (Prefix Tree)

MEDIUM

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:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints:

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

Approaches

Checkout 2 different approaches to solve Implement Trie (Prefix Tree). Click on different approaches to view the approach and algorithm in detail.

Array-based Approach

This approach uses a simple array to store characters and implements a basic trie structure. Each node in the trie contains a boolean flag to mark the end of a word and an array of size 26 (for lowercase English letters) to store child nodes.

Algorithm

Create a TrieNode class with an array of size 26 for children and a boolean flag
For insert:
- Start from root
- For each character, create a new node if it doesn't exist
- Mark the last node as end of word
For search:
- Traverse the trie following the characters
- Return true if last node exists and is marked as end of word
For startsWith:
- Similar to search but only check if path exists

In this approach, we create a TrieNode class that contains:

A boolean flag isEndOfWord to mark if the node represents the end of a word
An array of TrieNode references of size 26 for each possible lowercase letter

Here's the implementation:

class TrieNode {
    TrieNode[] children;
    boolean isEndOfWord;
    
    public TrieNode() {
        children = new TrieNode[26];
        isEndOfWord = false;
    }
}

class Trie {
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode current = root;
        for(char ch : word.toCharArray()) {
            int index = ch - 'a';
            if(current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }
    
    public boolean search(String word) {
        TrieNode node = searchNode(word);
        return node != null && node.isEndOfWord;
    }
    
    public boolean startsWith(String prefix) {
        return searchNode(prefix) != null;
    }
    
    private TrieNode searchNode(String str) {
        TrieNode current = root;
        for(char ch : str.toCharArray()) {
            int index = ch - 'a';
            if(current.children[index] == null) {
                return null;
            }
            current = current.children[index];
        }
        return current;
    }
}

Complexity Analysis

Time Complexity: O(m) for all operations, where m is the length of the word/prefixSpace Complexity: O(N * 26 * M) where N is the number of words and M is average word length. Each node contains an array of size 26.

Pros and Cons

Pros:

Simple implementation with array indexing
Constant time lookup for children (array access)
Memory efficient for small alphabets

Cons:

Fixed size array wastes space for sparse nodes
Not flexible for different character sets
Memory intensive for large character sets

Code Solutions

Checking out 5 solutions in different languages for Implement Trie (Prefix Tree). Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Implement Trie (Prefix Tree)

Patterns:

Design

Data Structures:

Hash TableStringTrie

Companies:

Docusign |DoorDash |Nvidia |Roblox |