Space

Open

From Fieldwork

Scales

642. Design Search Autocomplete System

leetcodeharddesigntriestringdata-streamsortingheappriority-queue

Open pinned source

v1

You rarely have to write the whole thing.

We can get away with writing 15 lines of code and "hand-waving" the rest.

Pattern 1: The "Trie Skeleton" (The Muscle Memory)

class TrieNode:
    def __init__(self):
        self.children = {}  # Map char -> Node
        self.is_word = False # Or store data here (like frequency)

Pattern 2: The "Crawler" (The Standard Loop)

Whether you are inserting a word or searching for a word, the code is identical. You are just crawling down the tree.

node = root
for char in word:
    if char not in node.children:
        # Create it (if inserting) OR Return False (if searching)
    node = node.children[char]
# Now 'node' is at the end of the prefix

Takeaway: This loop is the answer to everything.

Want to insert? Use the loop.
Want to search? Use the loop.
Want autocomplete? Use the loop to get to the prefix node, then worry about the top 3.

Pattern 3: The "Decoupled HashMap" (The Cheat Code)

Here is how you make the code much, much simpler (and easier to write).

Don't try to manage complex frequency counters inside the recursion. It's too messy.
Instead, keep a separate Global Hashmap for counting.

Trie: Handles the structure (finding the path).
HashMap: Handles the math (counting frequencies).

How this saves you:
When the user types # (enter), you don't need to traverse the tree to update counts. You just do global_map[sentence] += 1. Done.

Define the Class: Write class TrieNode.
Define the Dictionary: Write self.counts = {}.
Ask the "Lazy" Question:

"To find the Top 3, is it okay if I just traverse the sub-tree (DFS) for now? We can optimize it with caching later if we have time."

95% of interviewers will say "Yes."
Write the DFS (if asked):
The DFS is just: "Visit my children. If I am a word, add me to the list."

Summary

Problem: Autocomplete / Typeahead
Data Structure: Trie (Prefix Tree) + HashMap (for frequencies)

Key Concepts:

TrieNode: { children: Map, is_end: Bool }
Input(char): Traverse down one step. If valid, DFS from that point to gather results.
Input(#): Update HashMap[sentence] += 1 and Trie.insert(sentence).
Sorting: results.sort(key=lambda x: (-frequency, text))

Trade-off (The "Bonus Points" discussion):

Current approach (DFS): Slow Read (O(N)), Fast Write. Good for saving memory.
Optimized approach (Cache at Node): Fast Read (O(1)), Slow Write. Good for high-traffic search engines.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        # We store the full sentence at the leaf to make retrieval easier
        self.sentence = None 
        # We can store frequency at the leaf, 
        # but a global hashmap is often cleaner for updates.

class AutocompleteSystem:

    def __init__(self, sentences: list[str], times: list[int]):
        self.root = TrieNode()
        self.current_sentence = ""
        self.keyword_counts = {}  # Global map for frequency: sentence -> count
        
        # Initialize the system with historical data
        for i in range(len(sentences)):
            self.keyword_counts[sentences[i]] = times[i]
            self.add_to_trie(sentences[i])

    def add_to_trie(self, sentence):
        node = self.root
        for char in sentence:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
        node.sentence = sentence

    def input(self, c: str) -> list[str]:
        # CASE 1: End of sentence
        if c == '#':
            # Update frequency
            self.keyword_counts[self.current_sentence] = self.keyword_counts.get(self.current_sentence, 0) + 1
            # Ensure it's in the trie
            self.add_to_trie(self.current_sentence)
            # Reset buffer and return empty
            self.current_sentence = ""
            return []
        
        # CASE 2: Typing a character
        self.current_sentence += c
        
        # Traverse to the current prefix node
        node = self.root
        for char in self.current_sentence:
            if char not in node.children:
                return [] # Prefix doesn't exist
            node = node.children[char]
            
        # Perform DFS to find all sentences starting with this prefix
        results = []
        self.dfs(node, results)
        
        # Sort results: 
        # 1. Frequency (descending) -> -x[1]
        # 2. ASCII (ascending) -> x[0]
        results.sort(key=lambda x: (-x[1], x[0]))
        
        # Return top 3 sentences (extracting just the string)
        return [item[0] for item in results[:3]]

    def dfs(self, node, results):
        if node.is_end:
            count = self.keyword_counts[node.sentence]
            results.append((node.sentence, count))
            
        for child in node.children.values():
            self.dfs(child, results)

Practice bench

Continue the thread

A private scratchpad for this reading. Nothing is sent or scored.

You

What is still unclear, or what would change the explanation?

Saved on this device · one draft per mode

leetcodeNov 29, 2025