Implement Trie (Prefix Tree)

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() — Initializes the trie object.
• insert(word) — Inserts the string word into the trie.
• search(word) — Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• startsWith(prefix) — Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Examples

Example 1:

Input: operations = ["Trie","insert","search","search","startsWith","insert","search"], operands = [[],["apple"],["apple"],["app"],["app"],["app"],["app"]]

Output: [null,null,true,false,true,null,true]

Explanation: The Trie is initialized, then "apple" is inserted. Searching for "apple" returns true, but "app" returns false since only "apple" was inserted. However, startsWith("app") returns true because "apple" starts with "app". After inserting "app", searching for "app" returns true.

Example 2:

Input: operations = ["Trie","insert","insert","search","search","startsWith"], operands = [[],["hello"],["help"],["hell"],["hello"],["hel"]]

Output: [null,null,null,false,true,true]

Explanation: After inserting "hello" and "help", searching for "hell" returns false (not a complete word), "hello" returns true, and startsWith("hel") returns true.

Constraints

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters
• At most 3 * 10⁴ calls in total will be made to insert, search, and startsWith