Implement Trie

Problem: Implement Trie Implement a Trie, also known as a prefix tree, supporting the following operations: insert(word): Insert word into the Trie. search(word): Return true if word has been inserted as a complete word; otherwise return false. startsWith(prefix): Return true if any inserted word starts with prefix; otherwise return false. Input Format The first line contains an integer q, the number of operations. The next q lines each contain one of the following operations: insert word search word startsWith prefix Output Format For every search and startsWith operation, print true or false. insert does not produce output. Constraints 1 <= q <= 10^5 1 <= len(word), len(prefix) <= 100 Strings contain only lowercase English letters a-z. Example Input: 5 insert apple search apple search app startsWith app insert app Output: true false true Example Input 5 insert apple search apple search app startsWith app insert app Output true false true