Search Suggestions System

Problem Id: 1268 Difficulty: Medium Tag: String


Intuition

This problem could be solved using eigher sliding window or trie. And we will using sliding window here.

First, we will sort all the words. After it is sorted. We start to use sliding window algorithm. For example, if the search string is abc, then we need to query a, ab, and abc. For each query, the result is always a sub set of query result of previous one.

Solution


class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort()

        lo = 0
        hi = len(products) - 1
        ans = []
        for i, c in enumerate(searchWord):
            while lo <= hi and (len(products[lo]) <= i or products[lo][i] != c):
                lo += 1
            while lo <= hi and (len(products[hi]) <= i or products[hi][i] != c):
                hi -= 1
            if lo > hi:
                ans.append([])
            else:
                ans.append(products[lo:min(lo + 3, hi + 1)])
        return ans