Implement Trie
Let's play with words and magic trees!
In this challenge, you will implement a Trie (pronounced as "try"), which is a special type of tree used to store associative data structures. A common application of a Trie is in storing a predictive text or autocomplete functionality.
In our case, you'll be focusing on two main methods related to the trie structure:
- insert(word): This method inserts a word into the trie.
- search(word): This method checks if a given word exists in the trie.
Let's consider how these methods will work:
insert("cat")will ensure that the word "cat" is stored in the trie.search("cat")should returnTrueif "cat" was added to the trie, otherwiseFalse.- Similarly,
search("car")unless inserted, should returnFalse.
Below are some examples for better understanding:
trie = Trie() trie.insert("hello") print(trie.search("hello")) # Output: True print(trie.search("hell")) # Output: False trie.insert("hi") print(trie.search("hi")) # Output: True print(trie.search("bye")) # Output: False
Your task is to complete the Trie class with these two methods: insert and search.
Let's get creative and explore the magic of words stored efficiently!
How the tests work
Each test is a list of steps such as ["insert", "hello"] or ["search", "hell"], run in order on a new Trie. The test checks the results of the search steps, so the example above gives [true, false, true, false].
Inputs
Arg 1:
[["insert","hello"],["search","hello"],["search","hell"],["insert","hi"],["search","hi"],["search","bye"]]Expected Output
[true, false, true, false]Actual Output