LeetCode 642: Design Search Autocomplete System Solution in Python – A Step-by-Step Guide

What Is LeetCode 642: Design Search Autocomplete System?

In LeetCode 642: Design Search Autocomplete System, you’re tasked with implementing an AutocompleteSystem class that takes a list of historical sentences and their frequencies, and provides these methods:

• Constructor: Initialize with sentences (list of strings) and times (list of integers, frequencies).
• input(c): Process character c, return the top 3 sentences matching the current prefix, sorted by frequency (descending) and lexicographically (ascending) for ties.

The system tracks a prefix as the user types, updating it with each input(c) call. If c is '#', the current prefix is saved as a sentence with incremented frequency, and the prefix resets. For example, with sentences ["i love you", "island"], typing "i " returns ["i love you", "island"]. This problem tests your ability to design a search system with prefix matching and ranking.

Problem Statement

• Input:
• Constructor: sentences (list of strings), times (list of integers).
• input: c (character or '#').
• Output: A class with:
• Constructor: None (initializes system).
• input: List of up to 3 strings (top matches).
• Rules:
• Match sentences starting with current prefix.
• Rank by frequency (descending), then lexicographical order (ascending).
• '#' saves prefix as a sentence, resets prefix.

Constraints

• 1 ≤ sentences.length = times.length ≤ 100.
• 1 ≤ sentences[i].length ≤ 100.
• 1 ≤ times[i] ≤ 100.
• All characters are lowercase letters, space, or '#'.
• Up to 1000 calls to input.

Examples

• Input:
• ["AutocompleteSystem","input","input","input","input"]
• [["i love you","island","i love to code","ironman"],[5,3,2,2],["i"],[" "],["l"],["#"]]
• Output: [null,["i love you","island","i love to code"],["i love you","i love to code"],["island"],[]]
• "i" → top 3 with "i".
• "i " → top 2 with "i ".
• "il" → "island".
• "#" → save "il", reset.
• Input:
• ["AutocompleteSystem","input","input"]
• [["abc","abb","a"],[3,3,3],["a"],["b"]]
• Output: [null,["a","abb","abc"],["abb","abc"]]

These examples set the search—let’s solve it!

Understanding the Problem: Building Autocomplete

To solve LeetCode 642: Design Search Autocomplete System in Python, we need to design a class that stores historical sentences with frequencies, tracks a prefix as characters are input, and returns the top 3 matching sentences efficiently. A naive approach—scanning all sentences per input—would be O(n * m) per call (n = sentences, m = avg length), slow for 1000 calls. Since we’re matching prefixes, we can optimize with a trie or hash map. We’ll use:

• Best Solution (Trie-Based with Frequency Tracking): O(p + n log n) time per input, O(N) space—fast and scalable (p = prefix length, N = total chars).
• Alternative Solution (Hash Map with Sorting): O(n log n) time per input, O(N) space—simpler but less efficient.

Let’s start with the trie solution, breaking it down for beginners.

Best Solution: Trie-Based with Frequency Tracking

Why This Is the Best Solution

The trie-based approach with frequency tracking is the top choice for LeetCode 642 because it’s efficient—O(p + n log n) time per input with O(N) space—and leverages a trie (prefix tree) to quickly find all sentences matching the current prefix, sorting only the matches. It fits constraints (100 sentences, 1000 calls) and scales well for prefix queries. It’s like a smart search tree that grows with your history!

How It Works

Think of this as a prefix grower:

• Step 1: Initialize Trie:
• Build trie from sentences and times, storing frequency at sentence-ending nodes.
• Step 2: Input Character:
• Append c to prefix.
• If c ≠ '#':
• Traverse trie to prefix node.
• DFS to collect all sentences below, sort by frequency and lexicography, take top 3.
• If c = '#':
• Add prefix to trie with frequency +1, reset prefix.
• Step 3: Return Matches:
• List of up to 3 sentences.

It’s like a suggestion tree—grow and prune!

Step-by-Step Example

Example: sentences = ["i love you", "island"], times = [5, 3], inputs = "i "

• Step 1: Init:
• Trie: Root → i → {space: {l: {o: {v: {e: {space: {y: {o: {u: {freq: 5}}}}}}}, s: {l: {a: {n: {d: {freq: 3}}}}}}}.
• Prefix = "".
• Step 2: input('i'):
• Prefix = "i".
• Traverse to 'i' node, DFS: ["i love you" (5), "island" (3)].
• Top 3: ["i love you", "island"].
• Step 3: input(' '):
• Prefix = "i ".
• Traverse to ' ' node, DFS: ["i love you" (5)].
• Top 3: ["i love you"].
• Output: [null, ["i love you", "island"], ["i love you"]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass TrieNode:
    def __init__(self):
        self.children = {}
        self.freq = 0  # Frequency if sentence ends here

class AutocompleteSystem:
    def __init__(self, sentences: List[str], times: List[int]):
        # Step 1: Initialize trie and prefix
        self.root = TrieNode()
        self.prefix = ""

        # Build trie from sentences and times
        for sentence, freq in zip(sentences, times):
            node = self.root
            for char in sentence:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.freq = freq

    def input(self, c: str) -> List[str]:
        # Step 2: Process input character
        if c == '#':
            # Save prefix as sentence, reset
            node = self.root
            for char in self.prefix:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.freq += 1
            self.prefix = ""
            return []

        # Append to prefix and find matches
        self.prefix += c
        node = self.root
        for char in self.prefix:
            if char not in node.children:
                return []
            node = node.children[char]

        # Step 3: DFS to collect all sentences
        def dfs(node, curr_sentence, result):
            if node.freq > 0:
                result.append((curr_sentence, node.freq))
            for char, child in node.children.items():
                dfs(child, curr_sentence + char, result)

        matches = []
        dfs(node, self.prefix, matches)

        # Sort by frequency (desc) and lexicography (asc)
        matches.sort(key=lambda x: (-x[1], x[0]))
        return [match[0] for match in matches[:3]]

• Lines 1-5: TrieNode: Children map, frequency tracker.
• Lines 9-18: Init: Build trie from sentences/times.
• Lines 21-43: input:
• '#' saves prefix, resets.
• Else, append c, traverse trie, DFS for matches.
• Lines 46-50: DFS: Collect sentences with frequencies.
• Lines 53-54: Sort and return top 3.
• Time Complexity:
• Init: O(N) (N = total chars).
• Input: O(p + n log n) (p = prefix length, n = matches).
• Space Complexity: O(N)—trie size.

This is like a suggestion engine—fast and smart!

Alternative Solution: Hash Map with Sorting

Why an Alternative Approach?

The hash map with sorting approach uses a dictionary to store sentences and frequencies—O(n log n) time per input, O(N) space. It’s simpler, scanning all sentences per input, but less efficient due to sorting overhead. It’s like a basic search filter with a ranker!

How It Works

Picture this as a sentence sorter:

• Step 1: Init hash map with sentences and frequencies.
• Step 2: Input:
• Append c to prefix.
• If '#', save prefix, reset.
• Else, filter matching sentences, sort, take top 3.
• Step 3: Return matches.

It’s like a filter list—sort and pick!

Step-by-Step Example

Example: Same as above

• Init: Map = {"i love you": 5, "island": 3}.
• Input('i'): Prefix = "i", matches = ["i love you", "island"], top 3 = ["i love you", "island"].
• Input(' '): Prefix = "i ", matches = ["i love you"], top 3 = ["i love you"].

Code for Hash Map Approach

Copy codeclass AutocompleteSystem:
    def __init__(self, sentences: List[str], times: List[int]):
        self.freq = dict(zip(sentences, times))
        self.prefix = ""

    def input(self, c: str) -> List[str]:
        if c == '#':
            self.freq[self.prefix] = self.freq.get(self.prefix, 0) + 1
            self.prefix = ""
            return []

        self.prefix += c
        matches = [s for s in self.freq if s.startswith(self.prefix)]
        matches.sort(key=lambda x: (-self.freq[x], x))
        return matches[:3]

• Lines 4-5: Init: Map sentences to frequencies.
• Lines 8-15: input:
• '#' saves prefix, resets.
• Else, filter matches, sort, take top 3.
• Time Complexity: O(n log n) per input—sorting.
• Space Complexity: O(N)—hash map.

It’s a simple suggester—filter and rank!

Comparing the Two Solutions

• Trie-Based (Best):
• Pros: O(p + n log n) time, O(N) space, fast prefix matching.
• Cons: Trie complexity.
• Hash Map (Alternative):
• Pros: O(n log n) time, O(N) space, straightforward.
• Cons: Slower due to full scan/sort.

Trie wins for efficiency.

Additional Examples and Edge Cases

• Input: ["abc", "abb"], [1, 1], "a"
• Output: ["abc", "abb"].
• Input: Empty prefix → [].

Both handle these well.

Complexity Breakdown

• Trie: Init O(N), Input O(p + n log n), Space O(N).
• Hash Map: Init O(N), Input O(n log n), Space O(N).

Trie is optimal for queries.

Key Takeaways

• Trie: Prefix power—smart!
• Hash Map: Simple sorting—clear!
• Search: Autocomplete is fun.
• Python Tip: Tries rock—see Python Basics.

Final Thoughts: Suggest Those Searches

LeetCode 642: Design Search Autocomplete System in Python is a challenging design puzzle. Trie-based tracking offers speed and scalability, while hash map sorting provides a clear baseline. Want more? Try LeetCode 208: Implement Trie or LeetCode 676: Implement Magic Dictionary. Ready to suggest? Head to Solve LeetCode 642 on LeetCode and build that autocomplete today!