Leetcode - Implement Trie (Prefix Tree)

Question

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.

This is antrie question.

Idea

• Basically, we have our exposed trie node layer where we have in theory, nodes from a-z where we put all words beginning with a letter under its exposed node
• We use a Trie since the StarsWith function is very efficient (O(1)) time vs O(n) with a list implementation
• We use a TrieNode to implement a Trie, where a node has
  • Children (hashmap)
  • End of word (bool)
• Insert
  • When we insert a word (ex. apple) we insert (a→p→p→l→e) where “e” is marked as the end of a word, where any node can be marked as the end of a word
  • We can also reuse nodes, ex. if we insert “ape”, we would leverage the pre-existing a and p by checking if they exist before creating these new nodes, but create a new child node of p which is e, and we mark that as the end of a word
• Search
  • When we search, we are going character by character in a word, and we are checking if a node exists as a child for the character we are looking for
  • When we reach the end of a word, we need to check if the node is marked as the “end” of a word
• Starts with
  • Same as search except we don’t check for the end condition

Solution