Trie Data Structure Implementation

Design and implement a Trie (prefix tree) to perform the following operations:

• insert(word): Add a string "word" to the Trie.
• search(word): Verify if the string "word" exists in the Trie.
• startsWith(prefix): Determine if there is any string in the Trie that starts with the given prefix "prefix".

Example:

Input:

Q = 4
1 apple
2 apple
3 app
2 app

Output:

true
true
false

Explanation:

Performing operations as follows: insert "apple", search "apple" returns true, startsWith "app" returns true, search "app" returns false.

Constraints:

• 1 <= Q <= 5 * 104 where Q is the number of queries.
• 1 <= |word| ≤ 10 where |word| is the length of the input word.
• Words consist only of lowercase English letters a-z.

Note:

Implement the function without worrying about I/O operations, as it will be handled separately.