Implement Trie
Medium
Design a data structure that efficiently stores and retrieves strings. Specifically, implement a Trie (Prefix Tree) with the following operations:
insert(String word): Inserts a stringwordinto the trie.search(String word): Returnstrueif the stringwordis present in the trie (i.e., was inserted before), andfalseotherwise.startsWith(String prefix): Returnstrueif there is any string in the trie that starts with the given prefix, andfalseotherwise.
Example
insert("apple") search("apple") -> true search("app") -> false startsWith("app") -> true insert("app") search("app") -> true
Constraints
- All inputs are guaranteed to be lowercase English letters (
a-z). - The length of the input string is in the range
[1, 2000]. - The total number of calls to
insert,search, andstartsWithis at most3 * 10^4.
Our solution implements a Trie (Prefix Tree) by creating a TrieNode structure where each node represents a single character in the inserted word. The Trie class maintains a root node and provides three core methods: insert, search, and startsWith.
-
insert(String word): For each word, we traverse the Trie, character by character. If a character is not already present in the current node’s children, we create a new node for it. Once the word is fully inserted, we mark the last node as the end of the word (
isEndOfWord = true). -
search(String word): To check if a word exists in the Trie, we traverse the Trie from the root, following the nodes corresponding to each character in the word. If we reach the end of the word and the last node is marked as the end of a word, we return
true. Otherwise, we returnfalse. -
startsWith(String prefix): Similar to the
searchmethod, we traverse the Trie, but we do not require the last node to be marked as the end of a word. If we successfully traverse through all the characters of the prefix, we returntrue.
The Trie structure ensures efficient insertion and search operations by breaking down words into individual characters and storing them in a tree-like structure.
Time Complexity:
- The
insertmethod has a time complexity ofO(m), wheremis the length of the word being inserted. - The
searchandstartsWithmethods also have a time complexity ofO(m), wheremis the length of the word or prefix.
Space Complexity:
- The space complexity is
O(m * n), wherenis the number of words inserted into the Trie, andmis the average length of the words. This is because each node occupies constant space, and we create new nodes for each unique character.
Interview experiences
1 sharedRelated courses
