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
- Sort
productsonce. Then for each prefix, all matching products form a contiguous block starting atbisect_left(products, prefix). - Scan at most three entries from that index, stopping as soon as a product no longer starts with the prefix.
- The early stop is important: without it you might return products that merely sort after the prefix.
- 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
startswithcheck: 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.