Implement Trie (Prefix Tree)
Problem 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 stringwordinto the trie.boolean search(String word)Returnstrueif the stringwordis in the trie (i.e., was inserted before), andfalseotherwise.boolean startsWith(String prefix)Returnstrueif there is a previously inserted stringwordthat has the prefixprefix, andfalseotherwise.
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
Constraints:
1 <= word.length, prefix.length <= 2000wordandprefixconsist only of lowercase English letters.- At most 3 * 104 calls in total will be made to
insert,search, andstartsWith.
Solve it on LeetCode
Approaches
1. Basic Trie Implementation
Intuition:
The basic idea of a Trie is to store strings in a tree-like structure where each node represents a single character. Each path down the tree represents a string. We add two special features to our nodes:
- A way to know if they represent the end of a valid string.
- Pointers to traverse to the next node based on the next character.
We'll implement the basic Trie operations:
- Insert: Traverse character by character, creating nodes if they don't exist.
- Search: Traverse character by character to see if the whole word exists.
- StartsWith: Similar to search, but only checks if the prefix exists.
Code:
- Time Complexity:
- Insert: O(n), where n is the length of the word to insert.
- Search/StartsWith: O(n), where n is the length of the word/prefix to search.
- Space Complexity: O(n * m), where n is the number of words and m is the length of the longest word.
2. Optimized Trie Implementation with HashMap
Intuition:
Instead of using a fixed size array for the children nodes, we can use a HashMap to dynamically store only the necessary characters. This saves space, especially in cases where the alphabet size is large or the set of possible characters is sparse.
Code:
- Time Complexity:
- Insert: O(n), where n is the length of the word to insert.
- Search/StartsWith: O(n), where n is the length of the word/prefix to search.
- Space Complexity: In practice, it can be lower than using a fixed array due to dynamic allocation of children, especially if the set of possible characters is sparse.