SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem involves a list of products and a search word. The goal is to return a list of product suggestions for each character in the search word as it is typed. The list of products is first sorted, and for each prefix of the search word, up to three lexicographically smallest products that match the prefix are returned.

Intuition

By sorting the list of products, we can efficiently narrow down the potential matches as the search word is typed. The problem becomes easier to manage by focusing on the portion of the list that could match the current prefix, reducing unnecessary comparisons.

Approach

1. Sort the Products: Start by sorting the list of products lexicographically.
2. Iterate Through Search Word: For each character in the search word, refine the range of potential matches:
   • Move the left pointer to the first product that matches the current prefix.
   • Move the right pointer to the last product that matches the current prefix.
3. Collect Results: For each prefix, collect up to three products that match and add them to the result list.
4. Return Results: Continue the process for all prefixes and return the list of results.

Complexity

Time Complexity:

Sorting the products takes (O(P \log P)), where (P) is the number of products. For each character in the search word, we potentially adjust the left and right pointers, which could take (O(P)) in the worst case. The overall complexity is (O(P \log P + N \times P)), where (N) is the length of the search word.

Space Complexity:

The space complexity is (O(1)) for the pointers and auxiliary variables, not counting the space required to store the output list.

Code

C++

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        sort(products.begin(), products.end());
        vector<vector<string>> ans;
        int left = 0, right = products.size() - 1;

        for (int i = 0; i < searchWord.length(); i++) {
            char c = searchWord[i];
            vector<string> res;

            while (left <= right && (products[left].size() <= i || products[left][i] < c)) left++;
            while (left <= right && (products[right].size() <= i || products[right][i] > c)) right--;

            for (int j = 0; j < 3 && left + j <= right; j++) {
                res.push_back(products[left + j]);
            }
            ans.push_back(res);
        }

        return ans;
    }
};

Python

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort()
        ans = []
        left, right = 0, len(products) - 1

        for i in range(len(searchWord)):
            c = searchWord[i]
            res = []

            while left <= right and (len(products[left]) <= i or products[left][i] < c):
                left += 1
            while left <= right and (len(products[right]) <= i or products[right][i] > c):
                right -= 1

            for j in range(3):
                if left + j <= right:
                    res.append(products[left + j])
            ans.append(res)

        return ans

Java

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        List<List<String>> ans = new ArrayList<>();
        int left = 0, right = products.length - 1;

        for (int i = 0; i < searchWord.length(); i++) {
            char c = searchWord.charAt(i);
            List<String> res = new ArrayList<>();

            while (left <= right && (products[left].length() <= i || products[left].charAt(i) < c)) left++;
            while (left <= right && (products[right].length() <= i || products[right].charAt(i) > c)) right--;

            for (int j = 0; j < 3 && left + j <= right; j++) {
                res.add(products[left + j]);
            }
            ans.add(res);
        }

        return ans;
    }
}

JavaScript

/**
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
var suggestedProducts = function (P, S) {
    P.sort()
    let ans = [], left = 0, right = P.length - 1
    for (let i = 0; i < S.length; i++) {

        let c = S.charAt(i), res = []
        while (P[left]?.charAt(i) < c) left++
        while (P[right]?.charAt(i) > c) right--
        for (let j = 0; j < 3 && left + j <= right; j++)
            res.push(P[left + j])
        ans.push(res)
    }

    return ans
};