Implement Trie

Advanced

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 return True if "cat" was added to the trie, otherwise False.
  • Similarly, search("car") unless inserted, should return False.

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].

Geek
Inputs

Arg 1:

[["insert","hello"],["search","hello"],["search","hell"],["insert","hi"],["search","hi"],["search","bye"]]
Expected Output
[true, false, true, false]
Actual Output