Design search autocomplete system

String Depth-First Search Design Trie Sorting Heap (Priority Queue) Data Stream

49.9% acceptance

Mar 31, 2026

2186

204

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'). You are given a string array sentences and an integer array times both of length n where sentences[i] is a previously typed sentence and times[i] is the corresponding number of times the sentence was typed. For each input character except '#', return the top 3 historical hot sentences that have the same prefix as the part of the sentence already typed. Here are the specific rules: The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before. The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same hot degree, use ASCII-code order (smaller one appears first). If less than 3 hot sentences exist, return as many as you can. When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list. Implement the AutocompleteSystem class: AutocompleteSystem(String[] sentences, int[] times) Initializes the object with the sentences and times arrays. List input(char c) This indicates that the user typed the character c. Returns an empty array [] if c == '#' and stores the inputted sentence in the system. Returns the top 3 historical hot sentences that have the same prefix as the part of the sentence already typed. If there are fewer than 3 matches, return them all.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

struct AutocompleteSystem {
  freq: HashMap<String, i32>,
  current: String,
}

impl AutocompleteSystem {
  fn new(sentences: Vec<String>, times: Vec<i32>) -> Self {
    let mut freq = HashMap::new();
    for (s, t) in sentences.into_iter().zip(times.into_iter()) {
      *freq.entry(s).or_insert(0) += t;
    }
    AutocompleteSystem {
      freq,
      current: String::new(),
    }
  }

  fn input(&mut self, c: char) -> Vec<String> {
    if c == '#' {
      let sentence = std::mem::take(&mut self.current);
      *self.freq.entry(sentence).or_insert(0) += 1;
      return vec![];
    }
    self.current.push(c);
    let prefix = &self.current;
    let mut matches: Vec<(&String, &i32)> = self.freq.iter()
      .filter(|(s, _)| s.starts_with(prefix.as_str()))
      .collect();
    matches.sort_by(|a, b| b.1.cmp(a.1).then(a.0.cmp(b.0)));
    matches.into_iter().take(3).map(|(s, _)| s.clone()).collect()
  }
}