⚡Flashcard Drill➔
NeetCode #292LC-1268MediumBinary Search
← Back to All Problems

#292 · #1268 · Search Suggestions System(搜索推荐系统)

📌 Problem Statement & Constraints

You are given an array of strings products and a string searchWord. After typing each character of searchWord, return up to three lexicographically smallest product names that have the current prefix. Return the results as a list of lists. Constraints: 1 <= products.length <= 1000, 1 <= products[i].length, searchWord.length <= 1000.

💡 Core Algorithmic Approaches

  1. Sort products once. Then for each prefix, all matching products form a contiguous block starting at bisect_left(products, prefix).
  2. Scan at most three entries from that index, stopping as soon as a product no longer starts with the prefix.
  3. The early stop is important: without it you might return products that merely sort after the prefix.
  4. Sorting once gives O(n log n + |searchWord| * (log n + 3)) overall.

💻 Benchmark Python3 Implementation

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        from bisect import bisect_left
        products.sort()
        res = []
        prefix = ""
        for ch in searchWord:
            prefix += ch
            i = bisect_left(products, prefix)   # first product >= prefix
            cur = []
            for j in range(i, min(i + 3, len(products))):
                if products[j].startswith(prefix):
                    cur.append(products[j])
                else:
                    break                      # no further matches
            res.append(cur)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n + L log n) where L is the length of searchWord: the sort plus a binary search per prefix.
💾 Space Complexity
O(1) beyond the output (the sort is in place).

⚠️ Interview Pitfalls & Follow-ups

  • Scanning the whole product list for each prefix: O(n * L * m).
  • Omitting the startswith check: products that sort after the prefix but do not share it would be wrongly included.
  • Forgetting to break: the same issue, and it wastes iterations.
  • Sorting the products for each prefix: unnecessary; one sort suffices.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems