Design Search Autocomplete System

Examples:

Input: ["The quick brown fox jumps over the lazy dog", "The dog runs quickly", "The quick dog runs"], "The"

Output: ["The quick brown fox jumps over the lazy dog", "The dog runs quickly", "The quick dog runs"]

Explanation: The top 3 most frequent sentences that start with the prefix "The" are returned.

Solutions

Trie with Hash Table

Time: O(N * M)Space: O(N * M)

The solution uses a Trie data structure to store the sentences and a hash table to store the frequency of each sentence. The search function uses a depth-first search to find all sentences that start with the given prefix and then sorts them based on their frequency.

class AutocompleteSystem {
  constructor(sentences) {
    this.trie = {};

    this.frequency = {};

    for (let sentence of sentences) {
      let node = this.trie;

      for (let char of sentence) {
        if (!node[char]) node[char] = {};

        node = node[char];
      }

      node.end = true;

      this.frequency[sentence] = (this.frequency[sentence] || 0) + 1;
    }
  }

  search(prefix) {
    let node = this.trie;

    for (let char of prefix) {
      if (!node[char]) return [];

      node = node[char];
    }

    let sentences = [];

    this.dfs(node, prefix, sentences);

    sentences.sort((a, b) => this.frequency[b] - this.frequency[a]);

    return sentences.slice(0, 3);
  }

  dfs(node, sentence, sentences) {
    if (node.end) sentences.push(sentence);

    for (let char in node) {
      if (char !== 'end') this.dfs(node[char], sentence + char, sentences);
    }
  }
}

Constraints:

Examples:

Solutions

Trie with Hash Table

Follow-up: