---
# System prepended metadata

title: '**Leetcode筆記(Search Suggestions System)**'
tags: [Amazon, arrays, medium, leetcode]

---

# **Leetcode筆記(Search Suggestions System)**


:::info
:information_source: 題目 : Search Suggestions System, 類型 : arrays , 等級 : medium
日期 : 2024/02/14，2024/09/27
:::


### 嘗試
先sort完，list.sort()是直接改變列表

嘗試用兩步驟
一步驟先找到正確的boundary，用很直觀的確認當前letter index是否和c相同，把左右boundary都放在valid的letter上
二步驟是輸出3或更少的letter
重複從searchWord開始找到最後
```python
class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort() # edit the list directly
        res = list()

        l, r = 0, len(products) - 1
        for i, c in enumerate(searchWord):
            # set the valid boundary
            while l <= r and (len(products[l]) <= i or products[l][i] != c):
                l += 1
            while l <= r and (len(products[r]) <= i or products[r][i] != c):
                r -= 1    
            
            # return (3 or less) valid answer
            count = min(r - l + 1, 3)
            res.append(products[l : l + count])
        
        return res
```
2024/09/27
先把它sort成字母順序，用l和r去框住valid的單字。注意if條件，如果i已經大於單字長度，則這個單字必定不是推薦字，需要往下遍歷
```python
class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products = sorted(products)
        n = len(searchWord)
        l, r = 0, len(products) - 1
        res = []

        for i in range(n):
            while l <= r and ((i >= len(products[l])) or (searchWord[i] != products[l][i])):
                l += 1
            while l <= r and ((i >= len(products[r])) or (searchWord[i] != products[r][i])):
                r -= 1
            
            if r - l + 1 >= 3:
                temp = products[l : l + 3]
            else:
                temp = products[l : r + 1]
            
            res.append(temp)
        
        return res
```

---
### **優化**

```python

```
---



**思路**


**講解連結**
Search Suggestions System - Leetcode 1268 - Python
https://www.youtube.com/watch?v=D4T2N0yAr20
Provided by. Neetcode
