Close
Topic list
Implement Trie
HARD
41 mins
Tries
Topics (Covered in this problem)
Problem solved
Skill meter
Tries
-
-
Other topics
Problem solved
Skill meter
Strings
-
-
Matrices (2D Arrays)
-
-
-
-
Sorting
-
-
Binary Search
-
-
Stacks & Queues
-
-
Trees
-
-
Graph
-
-
Dynamic Programming
-
-
Greedy
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
Sensei
in DSA topics
Open the topic and solve more problems associated with it to improve your skills
Check out the skill meter for every topic
See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Implement Trie

Hard
0/120
Avg time to solve 41 mins
Share

Problem Statement

Implement Trie Data Structure to support these operations:

``````insert(word) - To insert a string "word" in Trie
search(word) - To check if string "word" is present in Trie or not.
startsWith(word) - To check if there is any string in the Trie that starts with the given prefix string "word".
``````

Three type of queries denote these operations:

``````Type 1: To insert a string "word" in Trie.
1 word

Type 2: To check if the string "word" is present in Trie or not.
2 word

Type 3: To check if there is any string in the Trie that starts with the given prefix string "word".
3 word
``````

Detailed explanation ( Input/output format, Notes, Constraints, Images )
Sample Input 1 :
``````5
1 hello
1 help
2 help
3 hel
2 hel
``````
Sample Output 1 :
``````true
true
false
``````
Explanation to Sample Input 1 :
``````Query 1: "hello" is inserted
Query 2: "help" is inserted
Query 3: "true" is printed as "help" is present
Query 4: "true" is printed as "hello" and "help" is present having the prefix "hel"
Query 5: "false" is printed as "hel" is not present
``````
Sample Input 2 :
``````10
1 aaaa
1 aaaaaa
1 bcd
2 aaaaa
3 aaaaa
3 bc
2 bc
1 bc
3 bcda
2 bc
``````
Sample Output 2 :
``````false
true
true
false
false
true
``````
Explanation to Sample Input 2 :
``````Query 1: "aaaa" is inserted
Query 2: "aaaaaa" is inserted
Query 3: "bcd" is inserted
Query 4: "false" is printed as "aaaaa" is not present
Query 5: "true" is printed as "aaaaaa" is present having the prefix "aaaaa"
Query 6: "true" is printed as "bcd" is present having the prefix "bc"
Query 7: "false" is printed as "bc" is not present
Query 8: "bc" is inserted
Query 9: "false" is printed as no word is present having the prefix "bcda"
Query 10: "true" is printed as "bc" is present
``````
Auto
Console