Implement Trie (Prefix Tree)
Design a trie that supports inserting words and searching words or prefixes.
Examples
Input: [["Trie","insert","search","search","startsWith","insert","search"],[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]]
Output: [null,null,true,false,true,null,true]
Input: [["Trie","insert","startsWith"],[[],["hello"],["he"]]]
Output: [null,null,true]
Hints
Implement the `Trie` class with a root node that uses a dictionary to store child nodes, where each key is a character and the value is another `Trie` node.
Add a boolean flag to each node to mark the end of a word, and ensure this flag is set to `True` only when a complete word is inserted.
For the `startsWith` method, traverse the trie character by character; if the traversal completes without missing any character, return `True`, otherwise return `False`.
Related Problems
Implement Trie (Prefix Tree)
Design a trie that supports inserting words and searching words or prefixes.