Design a class AutocompleteSystem that helps with word suggestions based on a given prefix.
You must implement the following methods:
insert(word: string): Inserts a word into the system.search(prefix: string): string[]: Returns all words in the system that start with the given prefix. The result can be in any order.
Example Inputs & Outputs
const system = new AutocompleteSystem();
system.insert('cat');
system.insert('car');
system.insert('carbon');
system.insert('dog');
system.search('ca'); // ['cat', 'car', 'carbon']
system.search('car'); // ['car', 'carbon']
system.search('do'); // ['dog']
system.search('z'); // []
Constraints & Edge Cases
- Words are lowercase English letters only.
- Prefixes can be empty strings — return all inserted words in that case.
- Duplicates may be inserted but only need to appear once in search results.
- Assume each
search is case-sensitive.
- Handle large number of insertions efficiently (use Trie, not brute force list scan).
