{x}
blog image

Implement Trie (Prefix Tree)

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 <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most 3 * 104 calls in total will be made to insert, search, and startsWith.

Solution Explanation: Implement Trie (Prefix Tree)

This problem requires implementing a Trie data structure. A Trie, or prefix tree, is a tree-like data structure used to efficiently store and retrieve keys in a dataset of strings. It's particularly useful for operations like autocomplete and spell-checking.

The solution involves creating a TrieNode class (implicitly or explicitly depending on the language) that represents a node in the Trie. Each node has an array (or similar structure) to store pointers to its children nodes (one for each character in the alphabet), and a boolean flag to indicate whether the node represents the end of a valid word.

The Trie class itself contains the root node of the Trie and methods for inserting words, searching for words, and checking for prefixes.

Core Operations:

  • insert(word): This method iterates through the characters of the input word. For each character, it checks if a child node exists for that character. If not, a new node is created. The process continues until the end of the word, at which point the isEnd flag of the final node is set to true.

  • search(word): This method traverses the Trie based on the input word. If a node for a character is not found along the way, the word is not in the Trie, and false is returned. If the traversal reaches the end of the word and the isEnd flag of the final node is true, the word is found, and true is returned.

  • startsWith(prefix): This method is similar to search but only needs to traverse the Trie until the end of the prefix. If it reaches the end of the prefix without encountering a missing node, it indicates that at least one word starts with that prefix, and true is returned.

Time and Space Complexity:

  • Time Complexity:

    • insert(word): O(m), where m is the length of the word. This is because we iterate through each character of the word once.
    • search(word): O(m), for the same reason as above.
    • startsWith(prefix): O(p), where p is the length of the prefix.

  • Space Complexity: O(N * m), where N is the number of words inserted and m is the maximum length of a word. In the worst case, each character in every word could lead to the creation of a new node.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, JavaScript, C#):

The provided code examples demonstrate the implementation of the Trie data structure in various programming languages. Each example implements the Trie class with the three required methods (insert, search, startsWith). The core logic remains consistent across all languages, although the syntax and data structures used vary. The use of arrays for children (or HashMap in Rust) allows for efficient O(1) access to child nodes based on the character. Helper functions like searchPrefix help keep the code clean and reusable. Note that the Rust example uses Rc and RefCell to handle shared ownership of nodes efficiently.

Example Usage (Python):

trie = Trie()
trie.insert("apple")
print(trie.search("apple"))  # Output: True
print(trie.search("app"))   # Output: False
print(trie.startsWith("app")) # Output: True
trie.insert("app")
print(trie.search("app"))   # Output: True

This demonstrates how to use the implemented Trie class to insert words, search for words, and check for prefixes. Similar usage patterns apply to the other language examples.