Problem Description

The problem requires implementing a Trie, also known as a prefix tree, which is a special type of tree used to store associative data structures. A trie stores keys in a way that makes it fast and efficient to retrieve them by their prefix. It can be used for various applications, notably for the efficient retrieval and storage of strings within a set for tasks like autocomplete or spell checking.

The task is to create a Trie class with the following operations:

• [Trie](/problems/trie_intro)(): A method to initialize the trie object.
• void insert(String word): This method inserts the string word into the trie.
• boolean search(String word): This method checks if the string word exists in the trie (i.e., it has been inserted before), returning true if it exists and false otherwise.
• boolean startsWith(String prefix): This method checks if there is any word in the trie that starts with the given prefix, returning true if such a word exists and false otherwise.

Intuition

The intuition for building a trie starts with the basic necessity of storing strings in a way that common prefixes are shared to save space and make search operations efficient. A Trie is a rooted tree where each node represents a common prefix of some strings. Each node might have up to 26 children (in the case of lowercase alphabetic characters) and a boolean flag indicating whether a word ends at this node.

Here's how we arrive at the solution:

1. Trie Structure: The Trie class is visualized as a tree where each node contains an array of 26 elements representing the possible lowercase alphanumeric children ('a' to 'z'), and a boolean marker that signifies the end of a word (is_end).

2. Insertion: To insert a word, we iterate through each character of the word, map it to the appropriate child index (by subtracting the ASCII value of 'a' from the character's ASCII value to keep it within a 0-25 range), and move to the corresponding child node, creating a new node if it doesn't exist. When the end of the word is reached, we mark is_end as true at the final node.

3. Search: Searching for a whole word is similar to insertion, but instead of creating new nodes, we just traverse the nodes corresponding to each character. If we reach the end of the word, we check the is_end flag to see if the word is a complete and distinct entry in our trie.

4. Prefix Search: To search for a prefix, the process is almost identical to the word search, but we don't need to check the is_end flag; any reachable node after traversing the prefix indicates that a word with that prefix exists in the trie.

The auxiliary method _search_prefix encapsulates the common logic of traversing the trie that is shared between searching for a complete word and checking for a word that starts with a given prefix.

Using such a structure allows operations like insert, search and prefix search to be performed in O(m) time complexity, where m is the length of the word or prefix being processed.

Learn more about Trie patterns.

Solution Approach

The implementation of the [Trie](/problems/trie_intro) class is based on the fundamental concepts of the trie data structure, which stores strings in such a way that all the descendants of a node share a common prefix associated with that node, with the root being an empty string. Here is a step-by-step breakdown of the implementation process and the algorithm used:

1. Initialization (__init__): Our trie is initialized with 26 children (one for each lowercase letter) set to None, indicating that there are no child nodes yet. Additionally, a boolean is_end is initialized to False, signifying that initially, no word ends at this node.

   self.children = [None] * 26
   self.is_end = False

2. Insert Method (insert): To insert a word, we iterate over each character in the word. We calculate the index for the children array by subtracting the ASCII value of 'a' from the character's ASCII value. If the child at this index is None, we create a new [Trie](/problems/trie_intro) node there. After processing each character, we set the is_end flag at the node corresponding to the last character to True, indicating the end of the word.

   for c in word:
       idx = ord(c) - ord('a')
       if node.children[idx] is None:
           node.children[idx] = [Trie](/problems/trie_intro)()
       node = node.children[idx]
   node.is_end = True

3. Search Method (search): The search method makes use of an internal method _search_prefix that is common between the search and startsWith methods. This method attempts to traverse the trie according to the given word. If traversal is successful and the final node's is_end is True, it means the word exists in the trie.

   node = self._search_prefix(word)
   return node is not None and node.is_end

4. Prefix Search Method (startsWith): Similar to the search method, startsWith uses _search_prefix. If we can traverse all the characters of the prefix in the trie, it means a word with that prefix exists, regardless of the is_end value.

   node = self._search_prefix(prefix)
   return node is not None

5. Searching Prefix (_search_prefix): This is an internal method that traverses the tree according to the given prefix or word. If any character is not found, it immediately returns None. If the traversal is completed, it returns the last node accessed, which represents the final character in the prefix or word.

   for c in prefix:
       idx = ord(c) - ord('a')
       if node.children[idx] is None:
           return None
       node = node.children[idx]
   return node

By following this approach, the operations of inserting a word or searching for a word/prefix are done in O(m) time, where m represents the length of the word or prefix. This effective utilization of a trie allows for fast insertions and searches while optimizing space as common prefixes are shared among entries.

Example Walkthrough

Let's walk through a small example using the solution approach outlined for the implementation of a Trie:

Suppose we want to execute the following operations:

1. Initialize the Trie.
2. Insert the word "apple".
3. Search for the word "apple".
4. Search for the word "app" to check if it exists as a complete word.
5. Check if a prefix "app" exists.

Let's begin with step-by-step operations on the Trie:

1. Initialization:

   We create a Trie object.

   trie = Trie()

   • At this point, the trie is empty, with only the root node, and no words are added.

2. Inserting the word "apple":

   We call insert("apple") on our trie.

   trie.insert("apple")

   • We iterate through each character in "apple".
     • For 'a', calculate the index (0) and go to the child node at index 0. As it is None, create a new Trie node there.
     • Repeat the process for 'p', 'p', 'l', and 'e'.
   • At the end of insertion, mark the is_end as True at the node representing 'e'.

3. Searching for the word "apple":

   We call search("apple").

   trie.search("apple") # Should return True

   • Internally _search_prefix method is called that goes through each character in "apple".
   • Since we just inserted "apple", each of these nodes exist, and the final node's is_end is True.
   • Therefore, it returns True as "apple" exists in the trie.

4. Searching for the word "app":

   We call search("app").

   trie.search("app") # Should return False

   • _search_prefix method is used to traverse for "app".
   • While 'a' and 'p' exist, the is_end at the second 'p' is False because we inserted "apple" and not "app".
   • Hence, it returns False, indicating "app" is not registered as a distinct word in the trie.

5. Checking if prefix "app" exists:

   We call startsWith("app").

   trie.startsWith("app") # Should return True

   • _search_prefix method is used to traverse the trie for "app".
   • Since nodes for 'a' and 'p' exist, and we do not care about is_end when checking for a prefix,
   • It returns True as there is a word in the trie that starts with "app" (which is "apple").

Through this example, you can see how each of the operations work and how the methods _insert, _search, and _search_prefix interact with each other to perform trie operations efficiently.

Solution Implementation

Time and Space Complexity

Time Complexity

• insert method: The time complexity is O(n), where n is the length of the word being inserted. This is because we iterate through each character of the word and perform constant time operations for each one.

• search method: The worst-case time complexity is also O(n), assuming that n is the length of the word being searched. This is similar to insert, as the method traverses the Trie, which takes time proportional to the length of the word.

• startsWith method: The worst-case time complexity is O(m), where m is the length of the prefix. This is due to traversing the Trie up to the depth of the prefix length.

• _search_prefix method (used by both search and startsWith): The time complexity here is O(p), where p is the length of the prefix. It is traversed only once for each method call.

Space Complexity

• The overall space complexity of the Trie is O(k * l), where k is the maximum number of children (26 in this case, for each letter of the English alphabet) and l is the average length of the word. This is due to storing a number of nodes proportional to the length of the word times the number of children each node can have (which is 26 here, for lowercase English letters).

• Each node contains an array of 26 pointers and a boolean flag, and the total space used grows with the number of nodes created, which is based on the number of words inserted and their lengths.

• Note that the space complexity does not scale with the number of insert/search operations, but with the number of unique characters in the Trie. This makes Tries space-efficient when storing large sets of words with overlapping prefixes.

Learn more about how to find time and space complexity quickly using problem constraints.