← 返回 microsoft 的题目列表Design and Implement Search Auto-Complete (Simplified)
类型：online_judge
Design and implement a simplified search auto-complete system.
The system maintains a dictionary of words and must support:
add(word): add word into the dictionary (duplicates can be ignored).
suggest(prefix): given a prefix, return all words that start with the prefix.
Requirements:
No frequency-based ranking is needed.
No Top-K restriction; return all matches.
For deterministic output, return suggestions in lexicographical ascending order.
Input (for coding judge)
Line 1: integer q (number of operations)
Next q lines:
ADD <word>
SUGGEST <prefix>
Output
For each SUGGEST, print one line containing all matched words (lexicographically sorted, space-separated). Print an empty line if there is no match.
Constraints
1 <= q <= 2*10^5
word and prefix contain only lowercase letters a-z
1 <= len(word) <= 50, 0 <= len(prefix) <= 50
Example
Input:
6
ADD apple
ADD app
ADD apply
SUGGEST app
SUGGEST a
SUGGEST b
Output:
app apple apply
app apple apply
Example
Input
6
ADD apple
ADD app
ADD apply
SUGGEST app
SUGGEST a
SUGGEST b
Output
app apple apply
app apple apply