Contact List Using Trie

Arista CloudVision can benefit from fast prefix-based lookup when operators search internal contacts by name. Implement a contact list using a trie, rather than scanning every stored name for each query.

You are given an array of operations. Each operation is one of:

1. ['add', name]: insert name into the contact list. Duplicate names should be stored only once.
2. ['search', name]: return true if the exact contact exists, otherwise false.
3. ['prefix', prefix]: return every stored contact beginning with prefix, sorted in lexicographic order.

Return one result for each search or prefix operation, in the same order those queries appear. Add operations do not produce results. Names contain only lowercase English letters and are non-empty.

Formal Specification

Implement build_contact_list(operations), where operations is a list of two-element lists of strings. Return a list containing booleans for exact searches and lists of strings for prefix searches.

Examples

Example 1

Input: [['add', 'alice'], ['add', 'alex'], ['search', 'alice'], ['prefix', 'al']]

Output: [true, ['alex', 'alice']]

alice exists, and both contacts begin with al; lexicographic ordering places alex first.

Example 2

Input: [['add', 'bob'], ['prefix', 'b'], ['search', 'bea']]

Output: [['bob'], false]

Only bob matches the prefix, and bea was never added.

Constraints

• 1 <= operations.length <= 10^4
• Each name or prefix has length at most 50
• The total number of characters in all operation strings is at most 5 * 10^5
• Names contain only lowercase English letters
• Prefix results must be returned in lexicographic order