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 <= 2000word and prefix consist only of lowercase English letters.3 * 104 calls in total will be made to insert, search, and startsWith.The key idea behind solving Implement Trie (Prefix Tree) is to design a data structure that efficiently stores strings and supports fast prefix queries. A Trie organizes characters in a tree-like structure where each node represents a character and paths from the root form words. Each node typically stores references to its children and a flag indicating whether a complete word ends at that node.
To build the structure, the insert operation iterates through each character of the word and creates nodes if they do not already exist. The search operation traverses the same path and checks the end-of-word marker, while startsWith only verifies that the prefix path exists in the trie.
This approach is efficient because operations depend only on the length of the input word or prefix rather than the number of stored words. Using arrays (for fixed alphabets like lowercase letters) or hash maps for children nodes allows flexible and scalable implementations.
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insert Word | O(L) | O(L) |
| Search Word | O(L) | O(1) |
| StartsWith Prefix | O(L) | O(1) |
take U forward
This approach involves creating a basic Trie data structure using a tree of nodes. Each node represents a character in a word. Starting from a root node, each character of the word is inserted sequentially, with branches representing the progression to subsequent characters. This forms a chain of nodes (linked in a tree-like manner) from the root to the nodes representing complete words. For searching, we traverse these nodes based on the characters of the input word or prefix to check for existence.
Time Complexity: Insert, search, and startsWith operations are O(m), where m is the length of the word/prefix.
Space Complexity: O(26 * n * m) in the worst case, where n is the number of inserted words and m is the average length of the words. Each insertion can potentially add m nodes with 26 possible children each.
1class TrieNode:
2 def __init__(self):
3 self.children = {}
4 self.is_end_of_word = False
In the Python implementation, we make use of a TrieNode class with a dictionary to store pointers to child nodes and a boolean attribute to denote if the node is the end of a word. The Trie class creates the root node as part of the constructor. The insert method processes the word character by character, adding nodes for characters that are missing in the current sequence. The search and startsWith methods traverse down the trie nodes based on the characters of word or prefix, verifying each node's presence accordingly and checking the is_end_of_word flag when necessary for search.
This approach relies on maps (or hashmaps) for storing children nodes dynamically. The advantage of using maps over arrays in this context arises from reduced space consumption when handling sparse trees since only existing characters are stored. Nodes manage their children using hash references, leading to more flexible branching.
Time Complexity: O(m) per operation where m is the word/prefix length.
Space Complexity: O(n * m), where n estimates the word count and m accounts for varying lengths since nodes only maintain necessary mappings.
1class TrieNode {
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A Trie stores characters along paths from the root, meaning every prefix naturally forms part of the structure. When searching for a prefix, you only need to follow the corresponding path instead of scanning all stored words. This makes prefix queries extremely efficient.
Yes, Trie-related problems are commonly asked in FAANG and other top tech interviews. They test understanding of custom data structures, string processing, and design skills. Variations often appear in problems involving autocomplete systems, dictionaries, and word search.
A Trie (Prefix Tree) is the best data structure for this problem because it stores words in a hierarchical character-based structure. Each node maintains children pointers using either arrays or hash maps. This design enables very fast prefix lookups compared to scanning a list of words.
The optimal approach is to use a Trie data structure where each node represents a character and contains links to its child nodes. Words are inserted character by character, allowing efficient prefix-based operations. This ensures insert, search, and prefix checks run in O(L) time where L is the word length.
The JavaScript version utilizes Map for storing node child references. Map is advantageous with its guaranteed key storability and inherent ordering. The insert method tracks through characters, setting or accessing nodes on the fly with hashmap properties. Searching evaluates characters' existence in path while confirming final node's end-markers during search. Prefix check seeks each character similarly ensuring entire path viability.