642. Design Search Autocomplete System
Explanation
To solve this problem, we can use a Trie data structure to store the search terms and their frequencies. We can then perform searches starting from the current input prefix and return the top k most frequent search terms that match the prefix.
The steps would be as follows:
- Build the Trie data structure to store the search terms along with their frequencies.
- Implement a search function that starts from the current input prefix and traverses the Trie to find all matching search terms.
- Use a priority queue to keep track of the top k most frequent search terms that match the prefix.
- Return the top k search terms with their frequencies.
Time complexity:
- Building the Trie: O(N * M), where N is the number of search terms and M is the average length of the search terms.
- Searching for autocomplete suggestions: O(K * M), where K is the number of suggestions to return.
- Space complexity: O(N * M) for storing the Trie.
class TrieNode {
Map<Character, TrieNode> children;
Map<String, Integer> counts;
public TrieNode() {
children = new HashMap<>();
counts = new HashMap<>();
}
}
class AutocompleteSystem {
TrieNode root;
String prefix;
public AutocompleteSystem(String[] sentences, int[] times) {
root = new TrieNode();
prefix = "";
for (int i = 0; i < sentences.length; i++) {
insert(sentences[i], times[i]);
}
}
private void insert(String sentence, int times) {
TrieNode curr = root;
for (char c : sentence.toCharArray()) {
TrieNode next = curr.children.get(c);
if (next == null) {
next = new TrieNode();
curr.children.put(c, next);
}
curr = next;
curr.counts.put(sentence, curr.counts.getOrDefault(sentence, 0) + times);
}
}
public List<String> input(char c) {
if (c == '#') {
insert(prefix, 1);
prefix = "";
return new ArrayList<>();
}
prefix += c;
TrieNode curr = root;
for (char pc : prefix.toCharArray()) {
TrieNode next = curr.children.get(pc);
if (next == null) {
return new ArrayList<>();
}
curr = next;
}
PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
(a, b) -> a.getValue() == b.getValue() ? a.getKey().compareTo(b.getKey()) : b.getValue() - a.getValue()
);
for (Map.Entry<String, Integer> entry : curr.counts.entrySet()) {
pq.offer(entry);
}
List<String> result = new ArrayList<>();
for (int i = 0; i < 3 && !pq.isEmpty(); i++) {
result.add(pq.poll().getKey());
}
return result;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.