Implement Trie (Prefix Tree)
Try to solve the Implement Trie (Prefix Tree) problem.
We'll cover the following
Statement
Trie is a tree-like data structure used to store strings. The tries are also called prefix trees because they provide very efficient prefix-matching operations. Implement a trie data structure with three functions that perform the following tasks:
- Insert (word): This inserts a word into the trie.
- Search (word): This searches the given word in the trie and returns TRUE, if found. Otherwise, return FALSE.
- Search prefix (prefix): This searches the given prefix in the trie and returns TRUE, if found. Otherwise, return FALSE.
Constraints:
-
word.length
,prefix.length
- The strings consist only of lowercase English letters.
- At most, calls in total will be made to the functions.
Examples
The Insert function does not return anything. The Search and Search prefix functions return TRUE if the input is found in the trie. Otherwise, they will return FALSE.
Create a free account to view this lesson.
By signing up, you agree to Educative's Terms of Service and Privacy Policy