Search Suggestions System in Python | Binary Search & Sorting | LeetCode75 #Python #TrieFree #Coding

In this LeetCode 75 problem, we design a system to generate search suggestions based on a given search word. Given a list of unique product strings and a search word, our goal is to return a list of lists where each inner list contains up to three lexicographically smallest products that start with the current prefix of the search word. If there are more than three matching products, we only return the first three. If no products match, the list will be empty.

Key Points:

Input:

products: an array of unique strings.

searchWord: a string for which suggestions are generated as the user types.

Output:

A list of lists, where each inner list represents the suggested products after each character of searchWord is typed.

Constraints:

The number of products is at most 1000.

The sum of the lengths of the products is at most 2×10⁴.

searchWord length is at most 1000.

Requirements:

Return suggestions for every prefix of searchWord.

Suggestions must be in lexicographical order.

At most three suggestions per prefix.

Approach: Sorting + Binary Search

Sort the Products:
Sort the list products lexicographically. This ensures that when we search for a prefix, the valid suggestions are in order.

Process Each Prefix of searchWord:
For each character appended to form the current prefix:

Use bisect_left to find the first product in the sorted list that is not less than the prefix.

From that index, collect up to three products that start with the prefix.

Append the list of suggestions for the current prefix to the final result.

Return the Result:
The final result is a list of suggestion lists corresponding to each prefix.

Benefits:

Efficiency: The overall time complexity is dominated by the sort
O(nlogn) and then for each prefix, a binary search
O(logn), making it efficient for the given constraints.

Simplicity: This approach avoids building a Trie and leverages Python's efficient sorting and binary search capabilities.

Python Code Implementation:

import bisect

class Solution:
def suggestedProducts(self, products, searchWord):
# Step 1: Sort the products lexicographically
result = []
prefix = ""

# Step 2: For each character in searchWord, build the prefix and get suggestions
for ch in searchWord:
prefix += ch
# Use binary search to find the first product that is not less than the prefix
suggestions = []
# Gather up to three products starting from the found index that match the prefix
for i in range(start, min(start + 3, len(products))):
if products[i].startswith(prefix):
else:
break

return result

# Example Usage:
sol = Solution()

# Expected Output: [["mobile","moneypot","monitor"], ["mobile","moneypot","monitor"], ["mouse","mousepad"], ["mouse","mousepad"], ["mouse","mousepad"]]

# Expected Output: [["havana"], ["havana"], ["havana"], ["havana"], ["havana"], ["havana"]]

Complexity Analysis:

Time Complexity: Sorting the products takes
O(nlogn). For each character in the search word (at most 1000), we perform a binary search
O(logn) and check up to 3 products, so overall it’s efficient.

O(m) for storing the result (where m is the length of searchWord).

#LeetCode75, #Python, #BinarySearch, #Sorting, #Coding, #Algorithms, #Autocomplete, #TrieFree, #CodingInterview