Solution: Search Suggestions System

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #1268 (Medium): Search Suggestions System

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Given an array of strings products and a string searchWord. We want to design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return list of lists of the suggested products after each character of searchWord is typed.

---

Examples:

Example 1:
Input:	products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output:	[ ["mobile","moneypot","monitor"], ["mobile","moneypot","monitor"], ["mouse","mousepad"], ["mouse","mousepad"], ["mouse","mousepad"] ]
Explanation:	products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"] After typing m and mo all products match and we show user ["mobile","moneypot","monitor"] After typing mou, mous and mouse the system suggests ["mouse","mousepad"]

Example 2:
Input:	products = ["havana"], searchWord = "havana"
Output:	[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Example 3:
Input:	products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output:	[["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

Example 4:
Input:	products = ["havana"], searchWord = "tatiana"
Output:	[[],[],[],[],[],[],[]]

---

Constraints:

• 1 <= products.length <= 1000
• There are no repeated elements in products.
• 1 <= Σ products[i].length <= 2 * 10^4
• All characters of products[i] are lower-case English letters.
• 1 <= searchWord.length <= 1000
• All characters of searchWord are lower-case English letters.

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

Despite the fact that the clues suggest a binary search and a trie, the optimal solution to this problem needs neither. The substrings formed by adding one letter at a time from the search word (S) are naturally already in lexicographical order, as are the results that we're instructed to push into our answer array (ans).

So if we sort the products array (P), we should only ever need to iterate through P once during the entire remaining process of the solution with a time complexity of O(N). A single binary search would only require log(N) time, but we'd have to perform M = S.length binary searches, so in total they would take O(M * log(N)) time, compared to the O(N) time of a simple iteration.

With constraints of 1000 on both M and N, the binary search route would max out at a worse time complexity than iteration. Regardless, the sort itself, which is required for both, requires O(N * log(N)) time already, so neither option can decrease the overall time complexity required.

So in order to only require a single pass through P, we should keep track of the current bounds for the range of matches (left, right), then we'll iterate through the characters (c) of S. At each iteration, we'll first want to move left forward and right back to narrow the range of matches based on the new value of c.

Then we can add the next three elements of P to our result array (res), as long as they fall inside the range [left, right]. Once that's done, we can add res to ans and move to the next iteration.

Once we've finished iterating through S, we can return ans.

• Time Complexity: O(N * log(N)) where N is the length of P
• Space Complexity: O(1) excluding output space required for ans

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

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
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def suggestedProducts(self, P: List[str], S: str) -> List[List[str]]:
        P.sort()
        ans, left, right = [], 0, len(P) - 1
        for i in range(len(S)):
            c, res = S[i], []
            while left <= right and (len(P[left]) == i or P[left][i] < c): left += 1
            while left <= right and (len(P[right]) == i or P[right][i] > c): right -= 1
            for j in range(3):
                if left + j > right: break
                else: res.append(P[left+j])
            ans.append(res)
        return ans

---

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public List<List<String>> suggestedProducts(String[] P, String S) {
        Arrays.sort(P);
        List<List<String>> ans = new ArrayList<>();
        int left = 0, right = P.length - 1;
        for (int i = 0; i < S.length(); i++) {
            List<String> res = new ArrayList<>();
            char c = S.charAt(i);
            while (left <= right && (P[left].length() == i || P[left].charAt(i) < c)) left++;
            while (left <= right && (P[right].length() == i || P[right].charAt(i) > c)) right--;
            for (int j = 0; j < 3 && left + j <= right; j++)
                res.add(P[left+j]);
            ans.add(res);
        }
        return ans;
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& P, string S) {
        sort(P.begin(), P.end());
        vector<vector<string>> ans;
        int left = 0, right = P.size() - 1;
        for (int i = 0; i < S.length(); i++) {
            vector<string> res;
            char c = S[i];
            while (left <= right && (P[left].length() == i || P[left][i] < c)) left++;
            while (left <= right && (P[right].length() == i || P[right][i] > c)) right--;
            for (int j = 0; j < 3 && left + j <= right; j++)
                res.push_back(P[left+j]);
            ans.push_back(res);
        }
        return ans;
    }
};

Comments

[Rohith V]

My Java Solution using Trie Data Structure :

class Solution {

    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()){
            int index = ch - 'a';
            if (node.child[index] == null) {
                node.child[index] = new TrieNode();
            }
            node = node.child[index];
            node.suggestion.offer(word);
            if (node.suggestion.size() > 3) {
                node.suggestion.pollLast();
            }
        }
    }

    public List<List<String>> search(String searchWord) {
        List<List<String>> result = new ArrayList<>();
        TrieNode node = root;
        for (char ch : searchWord.toCharArray()) {
            int index = ch - 'a';
            if (node != null) {
                node = node.child[index];
            }
            result.add(node == null ? Arrays.asList() : node.suggestion);
        }
        return result;
    }


    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        for (String product : products) {
            insert(product);
        }
        return search(searchWord);
    }
}

class TrieNode {
    TrieNode [] child = new TrieNode [26];
    LinkedList<String> suggestion = new LinkedList<>();
}


/*
Complexity depends on the process of building Trie and the length of searchWord. Building Trie cost time O(m * m * n), due to involving comparing String, which cost time O(m) for each comparison. Therefore,
Time: O(m * m * n + L), space: O(m * n + L * m) - including return list ans, where m = average length of products, n = products.length, L = searchWord.length().
*/