What is the time complexity of Implement Trie (Prefix Tree)?

The optimal solution has a time complexity of O(n).

What is the space complexity of Implement Trie (Prefix Tree)?

The space complexity is O(n*m).

What data structures are used to solve Implement Trie (Prefix Tree)?

This problem uses Hash Table, String, Design, Trie. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Implement Trie (Prefix Tree)?

Insight 1: A Trie is a tree-like data structure where each node represents a character, and paths from the root to a node represent prefixes or words. Insight 2: Using a hash table (or array in C) to store the children of each node allows for efficient lookup of characters.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Implement Trie (Prefix Tree) - LeetCode 208 Solution

Q: Which companies ask LeetCode 208. Implement Trie (Prefix Tree) in interviews?

This problem is frequently asked at Arista Networks, Block, Citadel, Docusign, DoorDash and 12 more companies.

Implement Trie (Prefix Tree) - Complete Solution Guide

Implement Trie (Prefix Tree) is LeetCode problem 208, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWit

Detailed Explanation

The problem requires implementing a Trie data structure, also known as a prefix tree. This data structure is specifically designed for efficient storage and retrieval of strings based on their prefixes. We need to implement three key functionalities: `insert(word)` to add a word to the Trie, `search(word)` to check if a word exists in the Trie, and `startsWith(prefix)` to determine if any word in the Trie starts with a given prefix. The input consists of a series of operations (insert, search, startsWith) performed on strings composed of lowercase English letters, and we must correctly return the results of search and startsWith operations.

Solution Approach

The solution implements a Trie using nested hash maps (or an array of node pointers in C). Each node in the Trie represents a character. The `insert` operation traverses the Trie, creating new nodes for characters that are not already present. The `search` operation traverses the Trie to find the complete word, returning true only if the path exists and the final node is marked as the end of a word. The `startsWith` operation traverses the Trie to find the prefix, returning true if the path exists, regardless of whether the final node is marked as the end of a word. The python, java and cpp implementations make use of hash maps to store node children. The C implementation makes use of a fixed-size array to do the same, but is limited to lowercase alphabet.

Step-by-Step Algorithm

Step 1: Initialization: Create a Trie object with a root node. This root node is typically an empty hash map (or array in C) that will hold references to child nodes.
Step 2: Insert: For each character in the word to be inserted, check if the current node has a child node corresponding to that character. If not, create a new node for that character and add it as a child of the current node. Move to the child node and repeat for the next character. After processing all characters, mark the final node as the end of a word.
Step 3: Search: For each character in the word to be searched, check if the current node has a child node corresponding to that character. If not, return false (word not found). Move to the child node and repeat for the next character. After processing all characters, check if the final node is marked as the end of a word. If yes, return true (word found), otherwise, return false.
Step 4: StartsWith: For each character in the prefix, check if the current node has a child node corresponding to that character. If not, return false (prefix not found). Move to the child node and repeat for the next character. After processing all characters, return true (prefix found), regardless of whether the final node is marked as the end of a word.

Key Insights

Insight 1: A Trie is a tree-like data structure where each node represents a character, and paths from the root to a node represent prefixes or words.
Insight 2: Using a hash table (or array in C) to store the children of each node allows for efficient lookup of characters.
Insight 3: A boolean flag at each node indicates whether a complete word ends at that node, which is crucial for differentiating between prefixes and complete words in the search function.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n*m)

Topics

This problem involves: Hash Table, String, Design, Trie.

Companies

Asked at: Arista Networks, Block, Citadel, Docusign, DoorDash, Grammarly, Lyft, MakeMyTrip, Mapbox, Nvidia, Pinterest, Roblox, Samsung, ServiceNow, Snowflake, X, instabase.

Implement Trie (Prefix Tree) | LeetCode 208

Medium

Hash Table String Design Trie

Time: O(n)Space: O(n*m)

Solution Code

Available in:

import java.util.HashMap;
import java.util.Map;

class Trie {

    private Map<Character, Object> root;

    public Trie() {
        this.root = new HashMap<>();
    }
    
    public void insert(String word) {
        Map<Character, Object> node = (Map<Character, Object>) root;
        for (char char_ : word.toCharArray()) {
            node = (Map<Character, Object>) ((Map<Character, Object>) node).computeIfAbsent(char_, k -> new HashMap<>());
        }
        ((Map<Character, Object>) node).put("is_end", true);
    }
    
    public boolean search(String word) {
        Map<Character, Object> node = (Map<Character, Object>) root;
        for (char char_ : word.toCharArray()) {
            node = (Map<Character, Object>) ((Map<Character, Object>) node).get(char_);
            if (node == null) {
                return false;
            }
        }
        return ((Map<Character, Object>) node).getOrDefault("is_end", false) != null;
    }
    
    public boolean startsWith(String prefix) {
        Map<Character, Object> node = (Map<Character, Object>) root;
        for (char char_ : prefix.toCharArray()) {
            node = (Map<Character, Object>) ((Map<Character, Object>) node).get(char_);
            if (node == null) {
                return false;
            }
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 208: Implement Trie (Prefix Tree) - Detailed explanation and solution approaches.

Topics

Hash Table String Design Trie

Companies

Arista NetworksBlockCitadelDocusignDoorDashGrammarlyLyftMakeMyTrip

Stats

Difficulty:Medium

Languages:4

Companies:17

Problem #:208

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

4 steps

1
Step 1: Initialization: Create a Trie object with a root node. This root node is typically an empty hash map (or array in C) that will hold references to child nodes.
2
Step 2: Insert: For each character in the word to be inserted, check if the current node has a child node corresponding to that character. If not, create a new node for that character and add it as a child of the current node. Move to the child node and repeat for the next character. After processing all characters, mark the final node as the end of a word.
3
Step 3: Search: For each character in the word to be searched, check if the current node has a child node corresponding to that character. If not, return false (word not found). Move to the child node and repeat for the next character. After processing all characters, check if the final node is marked as the end of a word. If yes, return true (word found), otherwise, return false.
4
Step 4: StartsWith: For each character in the prefix, check if the current node has a child node corresponding to that character. If not, return false (prefix not found). Move to the child node and repeat for the next character. After processing all characters, return true (prefix found), regardless of whether the final node is marked as the end of a word.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n*m)

📝

Why?

The time complexity is O(n) because, in each operation, we iterate through each character of the input word or prefix. The space complexity is O(m*n) because in the worst-case scenario the number of total nodes created equals the sum of lengths of all words inserted. Each node can have up to 26 children, but we're counting the number of nodes, not the number of edges emanating from a single node.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using a hash set for search and startsWith

Store all inserted words in a hash set. search(word) can then be done in O(1) time. startsWith(prefix) can be done by iterating through all the words in the hash set and checking if each starts with the given prefix.

Time: insert: O(n), search: O(1), startsWith: O(k*m), where k is the number of words in the hash set and m is the length of the prefix.Space: O(m*n), where n is the number of words inserted and m is the average length of the words.

Trade-offs: This approach provides faster search but a slower startsWith operation if the number of words stored is large. The Trie offers a better tradeoff when startsWith operations are frequent, especially for short prefixes.

✨

Key Insights

1Insight 1: A Trie is a tree-like data structure where each node represents a character, and paths from the root to a node represent prefixes or words.
2Insight 2: Using a hash table (or array in C) to store the children of each node allows for efficient lookup of characters.
3Insight 3: A boolean flag at each node indicates whether a complete word ends at that node, which is crucial for differentiating between prefixes and complete words in the search function.

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Inserting an empty string. The insert operation should handle this gracefully, typically by simply marking the root node as the end of a word.
Edge case 2: Searching for an empty string. The search operation should return true if the root node is marked as the end of a word, and false otherwise.
Edge case 3: startsWith an empty string. The startsWith operation should always return true, since an empty string is a prefix of any word (including no word).

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to mark the end of a word during the insert operation, leading to incorrect search results.

✗Common mistake 2: Incorrectly implementing the startsWith function to return true only if the prefix is a complete word, rather than if any word starts with the prefix.

✗Common mistake 3: Not handling the case where a word is a prefix of another word. For example, inserting 'app' then 'apple'. The node for 'p' in 'app' needs to be marked as the end of a word.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Autocomplete suggestions in search engines or text editors. A Trie can quickly find all words starting with a given prefix, allowing for efficient suggestion generation.

🏦Real-world scenario 2: Spell checking. A Trie can be used to efficiently check if a word is in a dictionary. Additionally, it can be used to suggest corrections for misspelled words based on words with similar prefixes.

🎮Real-world scenario 3: IP routing. Routers use Tries to determine the next hop for a packet based on the destination IP address prefix.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 29, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 7

❓

Frequently Asked Questions

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Implement Trie (Prefix Tree)"?

For this medium-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?