Top-K Autocomplete Suggestions
Problem Description
You are building an autocomplete feature for a search engine. You have a list of `(phrase, frequency)` pairs representing how often each phrase has been searched. Given a query prefix, return the top `k` most frequent phrases that start with that prefix, sorted in descending order of frequency. If two phrases have equal frequency, break ties alphabetically.
Write a function `autocompleteTopK(phrases, frequencies, prefix, k)` that returns the top-k results.
**Example 1:**
```
Input:
phrases = ["data science", "data structures", "data mining", "database", "dating"]
frequencies = [80, 95, 60, 75, 40]
prefix = "dat"
k = 3
Output: ["data structures", "data science", "database"]
```
**Example 2:**
```
Input:
phrases = ["go", "golang", "google", "gorilla", "gopher"]
frequencies = [50, 50, 90, 30, 50]
prefix = "go"
k = 4
Output: ["google", "go", "golang", "gopher"]
```
*Note: In Example 2, "go", "golang", and "gopher" all have frequency 50 and are sorted alphabetically among themselves.*
Constraints
- 1 <= phrases.length == frequencies.length <= 10000
- 1 <= phrases[i].length <= 100
- 1 <= frequencies[i] <= 10^6
- 1 <= prefix.length <= 50
- 1 <= k <= phrases.length
- All characters are lowercase English letters and spaces
Follow-up
Extend the solution to support O(P) query time by storing the top-k list directly at every trie node during insertion.
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.