Trie with Autocomplete
Hard · Data Structures
Implement a Trie (prefix tree) of non-empty lowercase words:
- insert(word) adds the word. Returns false if it was already stored, otherwise true.
- has(word) returns true only for stored words (not for prefixes).
- countPrefix(prefix) returns how many stored words start with prefix (the empty prefix matches all words).
- complete(prefix, limit) returns at most limit stored words starting with prefix, in alphabetical order.
- delete(word) removes the word and returns true (false if it was not stored). Other words must keep working, and nodes no word needs any more must be removed.
- nodeCount() returns the number of nodes below the root (one per character; words share their common prefix).
The driver runTrie(ops) returns the result of every operation.