Implement Trie
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.
A Trie is a tree-like data structure that stores strings, where each node represents a single character of the string. This structure allows for efficient search operations by traversing down the branches of the tree, making it suitable for tasks like auto-completion, dictionary lookups, and spell checking.
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.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def starts_with(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return TrueTime 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.
class TrieNode { constructor() { this.children = {}; this.isEndOfWord = false; } } class Trie { constructor() { this.root = new TrieNode(); } insert(word) { let node = this.root; for (const char of word) { if (!node.children[char]) { node.children[char] = new TrieNode(); } node = node.children[char]; } node.isEndOfWord = true; } search(word) { let node = this.root; for (const char of word) { if (!node.children[char]) { return false; } node = node.children[char]; } return node.isEndOfWord; } startsWith(prefix) { let node = this.root; for (const char of prefix) { if (!node.children[char]) { return false; } node = node.children[char]; } return true; } }