Hash Table
String
Design
Trie
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:
- `insert(word)` inserts the string `word` into the trie.
- `search(word)` returns `true` if the string `word` is in the trie (i.e., was inserted before), and `false` otherwise.
- `startsWith(prefix)` returns `true` if a previously inserted string `word` has the prefix `prefix`, and `false` otherwise.
In this harness, each test case inserts a list of words and then performs a single `search` or `startsWith` query, returning its boolean result.
Example 1
Input: insert("apple"); search("apple")
Output: true
Example 2
Input: insert("apple"); search("app")
Output: false
Example 3
Input: insert("apple"); startsWith("app")
Output: true
Constraints
- •
1 <= word.length, prefix.length <= 2000 - •
word and prefix consist only of lowercase English letters. - •
At most 3 * 10⁴ calls in total will be made to insert, search, and startsWith.
Time Complexity
O(L) per op