Implement Trie

Try to solve the Implement Trie 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:

  • 1≤1 \leq word.length, prefix.length ≤500\leq 500

  • The strings consist only of lowercase English letters.

  • At most, 10310^3 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.

Created with Fabric.js 3.6.6 Output Sample example 1Input root b a t Insert('bat')

1 of 7

Created with Fabric.js 3.6.6 Output Sample example 2Input root b a y t e Insert('bye')

2 of 7

Created with Fabric.js 3.6.6 Output Sample example 3Input root b o a y k t e Insert('ok')

3 of 7

Created with Fabric.js 3.6.6 Output Sample example 4Input root b o c a y k t e r y Insert('cry')

4 of 7

Created with Fabric.js 3.6.6 Output Sample example 5Input root b o c a y k t e r y Search('bye') TRUE

5 of 7

Created with Fabric.js 3.6.6 Output Sample example 6Input root b o c a y k t e r y Search('con') FALSE

6 of 7

Created with Fabric.js 3.6.6 Output Sample example 7Input root b o c a y k t e r y Search prefix('ba') TRUE

7 of 7

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Implement Trie

1

Given a trie with the words [bat, bag, make, broom, bait], what will be the output of the following query?

search('bait')
A)

TRUE

B)

FALSE

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Note: The game below is only for the Insert function.

Drag and drop the cards to rearrange them in the correct sequence.

Begin from the root node and iterate over the string one character at a time.

For each character, check if the current character exists as a child node of the current node.

If the character is found, move to that child node and continue to the next character.

If the character is not found, create a new node for that character, link it as a child of the current node, and move to the newly created node.

For the last character of the word, set a boolean variable to TRUE for the corresponding node to indicate the end of the word.

Try it yourself#

Implement your solution in trie.py in the following coding playground. You will need the provided supporting code to implement your solution.

Python
trie.py
trie_node.py
Input #1
Input #2
Implement Trie

Trie: Introduction

Solution: Implement Trie