#642 - Design Search Autocomplete System

Problem Description

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<String> 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

/**
 * @param {string[]} sentences
 * @param {number[]} times
 */
var AutocompleteSystem = function(sentences, times) {
  this.trie = {};
  this.current = '';
  this.root = this.trie;

  for (let i = 0; i < sentences.length; i++) {
    this.insert(sentences[i], times[i]);
  }
};

/**
 * @param {character} c
 * @return {string[]}
 */
AutocompleteSystem.prototype.input = function(c) {
  if (c === '#') {
    this.insert(this.current, 1);
    this.current = '';
    this.root = this.trie;
    return [];
  }

  this.current += c;
  if (!this.root[c]) {
    this.root[c] = {};
    this.root = this.root[c];
    return [];
  }

  this.root = this.root[c];
  const candidates = [];
  this.search(this.root, this.current, candidates);

  candidates.sort((a, b) => {
    if (a.count !== b.count) return b.count - a.count;
    return a.sentence < b.sentence ? -1 : 1;
  });

  return candidates.slice(0, 3).map(item => item.sentence);
};

AutocompleteSystem.prototype.insert = function(sentence, count) {
  let node = this.trie;
  for (const char of sentence) {
    if (!node[char]) node[char] = {};
    node = node[char];
  }
  node.isEnd = (node.isEnd || 0) + count;
};

AutocompleteSystem.prototype.search = function(node, prefix, candidates) {
  if (node.isEnd) {
    candidates.push({ sentence: prefix, count: node.isEnd });
  }

  for (const char in node) {
    if (char !== 'isEnd') {
      this.search(node[char], prefix + char, candidates);
    }
  }
};