Problem Statement
Design and implement a Trie (also known as a Prefix Tree). A trie is a tree-like data structure that stores a dynamic set of strings, and is particularly useful for searching for words with a given prefix.
Implement the Solution class:
Solution()Initializes the object.void insert(word)Insertswordinto the trie, making it available for future searches.bool search(word)Checks if the word exists in the trie.bool startsWith(word)Checks if any word in the trie starts with the given prefix.
Examples
-
Example 1:
- Input:
- Trie operations:
["Trie", "insert", "search", "startsWith"] - Arguments:
[[], ["apple"], ["apple"], ["app"]]
- Trie operations:
- Expected Output:
[-1, -1, 1, 1] - Justification: After inserting "apple", "apple" exists in the Trie. There is also a word that starts with "app", which is "apple".
- Input:
-
Example 2:
- Input:
- Trie operations:
["Trie", "insert", "search", "startsWith", "search"] - Arguments:
[[], ["banana"], ["apple"], ["ban"], ["banana"]]
- Trie operations:
- Expected Output:
[-1, -1, 0, 1, 1] - Justification: After inserting "banana", "apple" does not exist in the Trie but a word that starts with "ban", which is "banana", does exist.
- Input:
-
Example 3:
- Input:
- Trie operations:
["Trie", "insert", "search", "startsWith", "startsWith"] - Arguments:
[[], ["grape"], ["grape"], ["grap"], ["gr"]]
- Trie operations:
- Expected Output:
[-1, -1, 1, 1, 1] - Justification: After inserting "grape", "grape" exists in the Trie. There are words that start with "grap" and "gr", which is "grape".
- Input:
Constraints:
1 <= word.length, prefix.length <= 2000wordandprefixconsist only of lowercase English letters.- At most 3 * 10<sup>4</sup> calls in total will be made to insert, search, and startsWith.
Why this is a Trie problem
| What the question says | The signal it matches |
|---|---|
| "particularly useful for searching for words with a given prefix" | the questions are about prefixes |
| "bool startsWith(word) Checks if any word in the trie starts with the given prefix" | the wording mentions starts with |
| "stores a dynamic set of strings" | the input is a set of words, queried many times |
This is the build the structure itself variant: insert, search, and prefix search.
The closest alternative. A hash set of the words. It answers insert and search perfectly, in less code and less memory. The introduction says so: for exact membership a hash set is the better tool.
startsWith is what a set cannot do. Answering it from a set means testing every stored word against the prefix, so the cost grows with the dictionary. A trie walks one character at a time, so the cost is the length of the prefix and nothing else. Building this structure is the point of the lesson, because the four problems after it all rest on the same walk.
Solution
The trie is represented as a tree, where each node contains an array of pointers (or references) to its children and a boolean flag indicating if the current node marks the end of a word. When inserting or searching for a word, we start at the root node and navigate through the tree character by character until we either finish the operation or determine the word doesn't exist in the trie.
Now, let's break down the operations:
-
Insert:
- We begin at the root node.
- For every character in the word, check if there's a child node for it.
- If the child node doesn't exist, we create it.
- Navigate to the child node and repeat the process for the next character.
- Once the end of the word is reached, mark the current node as an endpoint of a word.
-
Search:
- Starting at the root, traverse the trie character by character.
- For every character in the word, check if there's a child node for it.
- If at any point there isn't a child node for the character, the word doesn't exist in the trie.
- If we can traverse the entire word and the last node is marked as an endpoint, the word exists in the trie.
-
StartsWith:
- The operation is similar to the search, but we don't need the last node to be an endpoint.
- If we can traverse the prefix without any missing nodes, there exists a word in the trie that starts with the given prefix.
Algorithm Walkthrough
Let's trace the first example, insert("apple") then search("apple") then startsWith("app"). Move through the steps one at a time:
Step 1. A trie stores words as paths. Every node holds one character, and following a path from the root spells out a prefix. Inserting, searching and asking about a prefix are all the same walk down from the root, one character at a time. The only difference is what each of them does at the end of the walk.
1 of 5
Code
Complexity Analysis
- Time Complexity:
- Insert: O(m), where m is the key length.
- Search and StartsWith: O(m) in the worst case scenario.
- Space Complexity: O(n * m), where n is the number of inserted keys and m is the average key length.