Trie Autocomplete

Trie Autocomplete

The prefix-tree behind every search box: insert a dictionary, then answer exact-word, prefix, and top-k suggestion queries in lexicographic order.

Requirements

• Words contain only lowercase letters a–z. The dictionary is a set: inserting the same word twice does not create a duplicate suggestion.
• search is exact-word membership; startsWith is prefix membership — a word is a prefix of itself.
• suggest returns the lexicographically smallest matches first, at most k of them, space-joined on one line. A word that is itself the prefix sorts before its extensions (app before apple).
• When suggest finds nothing (the prefix matches no inserted word), return the single character - — never an empty line.

API to implement

Implement the class Autocomplete. The I/O driver is already written in the starter code — it parses the command script below and calls your methods. You only implement the class.

| Command | Returns | Behavior | |---|---|---| | insert <word> | — | Add word (lowercase letters) to the dictionary. Inserting a word twice is a no-op — the dictionary is a set. | | search <word> | boolean | Return whether word was inserted as a complete word (not merely a prefix of one). | | startsWith <prefix> | boolean | Return whether any inserted word begins with prefix (an empty-match returns false). | | suggest <prefix> <k> | string | Return up to k inserted words that start with prefix, in lexicographic order, joined by single spaces. If no word has that prefix, return the literal -. |

Input format

The first line contains Q, the number of operations. Each of the next Q lines is one command as listed above. String arguments contain no spaces.

Output format

For each command with a non-void return, print its result on its own line, in order. The driver does this for you — your methods just return values.

This is a design problem: the hidden tests exercise edge cases and interaction sequences, not performance tricks. Model the state cleanly and the tests will pass.

7
insert apple
insert app
insert apply
search app
search ap
startsWith ap
suggest ap 5

true
false
true
app apple apply

7
insert dog
insert dot
insert dorm
suggest do 2
suggest cat 3
startsWith do
search do

dog dorm
-
true
false