1268. Search Suggestions System - Explanation

1. Brute Force

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

        for i in range(m):
            cur = []
            for w in products:
                if len(w) <= i:
                    continue

                flag = True
                for j in range(i + 1):
                    if w[j] != searchWord[j]:
                        flag = False
                        break

                if flag:
                    cur.append(w)
                    if len(cur) == 3:
                        break

            if not cur:
                for j in range(i, m):
                    res.append([])
                break
            res.append(cur)

        return res

Time & Space Complexity

Time complexity: $O(n \log n + m * n)$
Space complexity:
- $O(n)$ or $O(1)$ space for the sorting algorithm.
- $O(m * w)$ space for the output array.

Where $n$ is the total number of characters in the string array $products$ , $m$ is the length of the string $searchWord$ , and $w$ is the average length of each word in the given string array.

2. Sorting + Binary Search

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

        prefix = []
        start = 0

        def binary_search(target, start):
            l, r = start, len(products)
            while l < r:
                mid = l + (r - l) // 2
                if products[mid] >= target:
                    r = mid
                else:
                    l = mid + 1
            return l

        for i in range(m):
            prefix.append(searchWord[i])
            start = binary_search("".join(prefix), start)

            cur = []
            for j in range(start, min(start + 3, len(products))):
                if products[j].startswith("".join(prefix)):
                    cur.append(products[j])
                else:
                    break

            res.append(cur)

        return res

Time & Space Complexity

Time complexity: $O(n \log n + m * w * \log N)$
Space complexity:
- $O(n)$ or $O(1)$ space for the sorting algorithm.
- $O(m * w)$ space for the output array.

Where $n$ is the total number of characters in the string array $products$ , $N$ is the size of the array $products$ , $m$ is the length of the string $searchWord$ , and $w$ is the average length of each word in the given string array.

3. Sorting + Binary Search (Built-In Function)

Python
C++

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

        prefix = ""
        start = 0
        for i in range(m):
            prefix += searchWord[i]
            start = bisect_left(products, prefix, start)

            cur = []
            for j in range(start, min(start + 3, len(products))):
                if products[j].startswith(prefix):
                    cur.append(products[j])
                else:
                    break

            res.append(cur)

        return res

Time & Space Complexity

Time complexity: $O(n \log n + m * w * \log N)$
Space complexity:
- $O(n)$ or $O(1)$ space for the sorting algorithm.
- $O(m * w)$ space for the output array.

Where $n$ is the total number of characters in the string array $products$ , $N$ is the size of the array $products$ , $m$ is the length of the string $searchWord$ , and $w$ is the average length of each word in the given string array.

4. Sorting + Two Pointers

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

        l, r = 0, len(products) - 1
        for i in range(len(searchWord)):
            c = searchWord[i]

            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

            res.append([])
            remain = r - l + 1
            for j in range(min(3, remain)):
                res[-1].append(products[l + j])

        return res

Time & Space Complexity

Time complexity: $O(n \log n + m * w + N)$
Space complexity:
- $O(n)$ or $O(1)$ space for the sorting algorithm.
- $O(m * w)$ space for the output array.

Where $n$ is the total number of characters in the string array $products$ , $N$ is the size of the array $products$ , $m$ is the length of the string $searchWord$ , and $w$ is the average length of each word in the given string array.