# **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開始找到最後

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已經大於單字長度，則這個單字必定不是推薦字，需要往下遍歷

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

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

---

**思路**

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