Trie — Insert, Search and Prefix
Practice this coding question on Coding Gurukul.
Problem statement
Implement a trie for lowercase English words. Start empty. - INSERT word: store the word. - SEARCH word: print YES if the complete word was inserted, otherwise NO. - PREFIX word: print YES if any inserted word starts with this string, otherwise NO. Inserting the same word again has no effect. A prefix is not a complete word unless it was inserted separately. INSERT produces no output. Use O(word length) time per command. Worked example After inserting apple, SEARCH app prints NO but PREFIX app prints YES. Inserting app makes SEARCH app print YES. SEARCH ape still prints NO.
Input format
First line: q. Next q lines: INSERT word, SEARCH word, or PREFIX word.
Output format
One YES or NO per SEARCH or PREFIX.
Constraints
1 <= q <= 100000; total number of input characters <= 200000. At least one query.
Sample input
6 INSERT apple SEARCH app PREFIX app INSERT app SEARCH app SEARCH ape
Sample output
NO YES YES NO
Sign in to run or submit a solution in C++, Java or Python.