# LeetCode: 1268. 搜索推荐系统¶

## 1、题目描述¶

输入：products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"

["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
]



输入：products = ["havana"], searchWord = "havana"



输入：products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"



输入：products = ["havana"], searchWord = "tatiana"



• 1 <= products.length <= 1000
• 1 <= Σ products[i].length <= 2 * 10^4
• products[i] 中所有的字符都是小写英文字母。
• 1 <= searchWord.length <= 1000
• searchWord 中所有字符都是小写英文字母。

## 2、解题思路¶

• 首先对字符串进行排序
• 然后利用二分法进行查找，找到当前前缀对应的位置，并尝试向后找出三个满足条件的三个单词
import bisect

class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
length = len(products)
products.sort()
search_index = 0
ans = []
for i in range(1, len(searchWord) + 1):
left = bisect.bisect_left(products, searchWord[:i], search_index)
temp = []
for j in range(3):
if left + j < length and products[left + j].startswith(searchWord[:i]):
temp.append(products[left + j])
ans.append(temp)
search_index = left
return ans