Problem Statement
Design and implement a Trie (also known as a Prefix Tree). A trie is a treelike data structure that stores a dynamic set of strings, and is particularly useful for searching for words with a given prefix.
Implement the Solution
class:
Solution()
Initializes the object.void insert(word)
Insertsword
into the trie, making it available for future searches.bool search(word)
Checks if the word exists in the trie.bool startsWith(word)
Checks if any word in the trie starts with the given prefix.
Examples

Example 1:
 Input:
 Trie operations:
["Trie", "insert", "search", "startsWith"]
 Arguments:
[[], ["apple"], ["apple"], ["app"]]
 Trie operations:
 Expected Output:
[1, 1, 1, 1]
 Justification: After inserting "apple", "apple" exists in the Trie. There is also a word that starts with "app", which is "apple".
 Input:

Example 2:
 Input:
 Trie operations:
["Trie", "insert", "search", "startsWith", "search"]
 Arguments:
[[], ["banana"], ["apple"], ["ban"], ["banana"]]
 Trie operations:
 Expected Output:
[1, 1, 0, 1, 1]
 Justification: After inserting "banana", "apple" does not exist in the Trie but a word that starts with "ban", which is "banana", does exist.
 Input:

Example 3:
 Input:
 Trie operations:
["Trie", "insert", "search", "search", "startsWith"]
 Arguments:
[[], ["grape"], ["grape"], ["grap"], ["gr"]]
 Trie operations:
 Expected Output:
[1, 1, 1, 1, 1]
 Justification: After inserting "grape", "grape" exists in the Trie. There are words that start with "grap" and "gr", which is "grape".
 Input:
Constraints:
1 <= word.length, prefix.length <= 2000
word
and prefix
consist only of lowercase English letters. At most 3 * 10<sup>4</sup> calls in total will be made to insert, search, and startsWith.
Try it yourself
Try solving this question here:
Python3
Python3