96. Implement Trie

Medium · Design

Implement a Trie (prefix tree) data structure that supports efficient insertion and search of strings. A Trie is a tree-like structure where each node represents a character, and paths from root to leaf nodes form words.

You must implement the following operations: - `insert(word)`: Add a word to the Trie. - `search(word)`: Return true if the word exists in the Trie, false otherwise. - `startsWith(prefix)`: Return true if there is any word in the Trie that starts with the given prefix, false otherwise.

Examples

Example 1
Input: Operations: insert('apple'), insert('app'), search('apple'), search('app'), search('appl'), startsWith('app'), startsWith('xyz')
Output: Results: [null, null, true, true, false, true, false]
Explanation: After inserting 'apple' and 'app', searching for 'apple' and 'app' returns true. Searching for 'appl' (incomplete word) returns false. startsWith('app') returns true because both words start with 'app'. startsWith('xyz') returns false.
Example 2
Input: Operations: insert('cat'), search('cat'), search('car'), startsWith('ca')
Output: Results: [null, true, false, true]
Explanation: After inserting 'cat', we can find it with search. 'car' is not in the Trie. The prefix 'ca' matches 'cat'.

Constraints