Implement a trie (prefix tree) with the following methods:
Trie() initializes the trie object.
void insert(String word) inserts the string word into the trie.
int search(String word) returns the value associated with the key word if the word exists in the trie, otherwise returns -1.
bool startsWith(String prefix) returns true if there is any previously inserted word that starts with the given prefix, otherwise returns false.This problem asks you to implement a Trie (prefix tree) that supports insertion, exact-word search, and prefix checks. The key idea is to store words character by character in a tree, using child pointers or a map at each node and marking word-ending nodes explicitly. All operations run in time proportional to the length of the input string, which makes the Trie especially useful for efficient string lookup and prefix matching.
END
