A trie for an autocomplete box

Autocomplete over a big list of commands, tags or city names gets slow if every keystroke filters the entire array. A trie stores words character by character so a prefix lookup walks only as far as the prefix is long.

Implement a Trie class. It is constructed with no arguments and starts empty. insert(word) stores a lowercase word; inserting the same word twice has no additional effect and its return value is not used. has(word) returns true only when that exact word was inserted, and false for a mere prefix of one. startsWith(prefix) returns true when at least one stored word begins with the prefix. complete(prefix) returns an array of every stored word beginning with the prefix, sorted alphabetically ascending, and returns [] when nothing matches. A word counts as beginning with itself, and complete('') returns every stored word.

What it has to do

• complete(prefix) returns matching words sorted alphabetically ascending.
• complete(prefix) includes the prefix itself when it was inserted as a word.
• complete(prefix) returns [] when no word matches.
• has is true only for full inserted words, while startsWith is true for any stored prefix.
• Inserting the same word twice does not duplicate it in the results.

Your workspace