Published: Sep 10, 2022

## Introduction

This is a prefix search problem. The size of prefix gets longer in each search. Trie is a good data structure for this type of problems. However, binary search is another good way to find the answer. Since the problem asks “lexicographically minimums,” input data should be sorted at the beginning. If the language is Python, binary search is a good algorithm to apply. Python’s binary search function supports string like a number.

## Problem Description

You are given an array of strings

`products`

and a string`searchWord`

. Design a system that suggests at most three product names from`products`

after each character of`searchWord`

is typed. Suggested products should have common prefix with`searchWord`

. If there are more than three products with a common prefix, return the three lexicographically minimums products.Return a list of lists of the suggested products after each character of

`searchWord`

is typed.Constraints:

`1 <= products.length <= 1000`

`1 <= products[i].length <= 3000`

`1 <= sum(products[i].length) <= 2 * 104`

- All the strings of products are unique.
`products[i]`

consists of lowercase English letters.`1 <= searchWord.length <= 1000`

`searchWord`

consists of lowercase English letters.

## Examples

```
Example 1:
Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"].
```

```
Example 2:
Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
```

## Analysis

The solution here uses the binary search.
The `products`

list is sorted at the beginning.
The prefix will be extended a character by character.
Do bisect_left with the prefix, then add up to 3 words with the same prefix to the result.

## Solution

```
class SearchSuggestionsSystem:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
products.sort()
result = []
for i in range(len(searchWord)):
prefix = searchWord[:i + 1]
sub = []
idx = bisect.bisect_left(products, prefix)
while idx < len(products) and len(sub) < 3 and products[idx][:i + 1] == prefix:
sub.append(products[idx])
idx += 1
result.append(sub)
return result
```

## Complexities

- Time:
`O(n*log(n))`

- Space:
`O(1)`