Practice/Google/Leetcode 642. Design Search Autocomplete System

Leetcode 642. Design Search Autocomplete System

CodingMust

Problem

Build a real-time search suggestion engine that provides autocomplete functionality. The system processes user input character by character and returns the top 3 most relevant search suggestions based on historical search data.

Your system must:

• Initialize with a collection of historical search sentences and their frequency counts
• Process one character at a time as the user types
• Return up to 3 suggestions matching the current input prefix
• Rank suggestions by frequency (highest first), breaking ties alphabetically
• Save new searches when the user completes input with a special termination character '#'

When the user types '#', the current input sequence is saved as a new search (or increments the frequency if it already exists), and the system resets for the next query.

Requirements

1. Implement a class with a constructor that takes two arrays: sentences (strings) and times (their corresponding frequencies)

2. Implement an input(c) method that:

   • Takes a single character c as input
   • Returns a list of up to 3 matching sentences if c is not '#'
   • Saves/updates the current sentence and returns an empty list if c is '#'

3. Results must be sorted by frequency (descending), then lexicographically (ascending) for ties

4. Only return sentences that match the accumulated prefix from previous inputs

Constraints

• 1 ≤ sentences.length ≤ 100
• 1 ≤ sentences[i].length ≤ 100
• 1 ≤ times[i] ≤ 50
• c is a lowercase letter, space, or '#'
• At most 5000 calls will be made to input
• Sentences contain only lowercase letters and spaces

Examples

Example 1:

Initialize: sentences = ["mobile phone", "mouse pad", "monitor"], times = [10, 5, 8] Input: 'm' → ["mobile phone", "monitor", "mouse pad"] Input: 'o' → ["mobile phone", "monitor", "mouse pad"] Input: 'u' → ["mouse pad"] Input: '#' → []

Explanation: After 'm', all three sentences match and are ranked by frequency. After 'mo', the same three still match. After 'mou', only "mouse pad" matches. The '#' saves "mou" as a new sentence with frequency 1.

Example 2:

Initialize: sentences = ["best buy", "best price", "best deal"], times = [3, 3, 3] Input: 'b' → ["best buy", "best deal", "best price"] Input: 'e' → ["best buy", "best deal", "best price"]

Explanation: All three sentences have the same frequency, so they're sorted alphabetically. Only the top 3 are returned.

Example 3:

Initialize: sentences = ["hello world"], times = [1] Input: 'h' → ["hello world"] Input: 'e' → ["hello world"] Input: 'l' → ["hello world"] Input: 'l' → ["hello world"] Input: 'o' → ["hello world"] Input: ' ' → ["hello world"] Input: 'w' → ["hello world"] Input: 'o' → ["hello world"] Input: 'r' → ["hello world"] Input: 'l' → ["hello world"] Input: 'd' → ["hello world"] Input: '#' → []

Explanation: The sentence matches at each step. After '#', the frequency of "hello world" becomes 2.