Leetcode 1268. Search Suggestions System

Problem Explanation:

This problem is about implementing an auto-suggest feature. Here, we are given a list of product names (products) and a searchWord. Our task is to create a suggestion system that, after each character of searchWord is typed, suggests at most three product names from products. The suggested products should have a common prefix with what has been typed of searchWord so far. If there is more than three products with a common prefix, the system should return the three lexicographically smallest products.

For instance, if products is ["mobile","mouse","moneypot","monitor","mousepad"] and searchWord is "mouse", after typing 'm' and 'mo', all products are valid suggestions but only the three lexicographically smallest are chosen i.e., ["mobile","moneypot","monitor"]. After typing 'mou', 'mous', and 'mouse', the system suggests ['mouse', 'mousepad'] because these are the only products that start with these prefixes.

Solution Approach:

The given problem can be solved effectively using a Trie data structure (a type of tree used for efficient retrieval of key in a large dataset of strings). Each node of the Trie represents one character and the root represents an empty string.

Briefly, the solution to this problem is divided into these steps:

1. Insertion: Insert all product names into the Trie.

2. Search: For each character present in searchWord, traverse the Trie and collect the lexicographically smallest products that have common prefix with the search word typed so far. For this, we use Depth First Search (DFS) on the Trie. Continue doing this until three such products are found or we have explored all products.

Let's illustrate this through a small example:

Consider an example where products is ["mobile","mouse","moneypot","monitor","mousepad"] and searchWord is "mouse". After building the Trie, our Trie would like below:

1
2
3Root
4|
5m - o -
6|   |
7b   n - e - y - p - o - t
8    |
9    u - s - e
10    |
11    u - s - e - p - a - d

Here, each node on path m-o-b-i-l-e denotes product name 'mobile', m-o-n-e-y-p-o-t denotes 'moneypot', and so on.

When we start typing searchWord, firstly, we type 'm'. We traverse the Trie from root node through 'm'. Since, we can't find even three products, we return all products which start with 'm'. After that, we type 'o', we continue our traversal from 'm' to 'o'. Since, still we can't find even three products, we return all products which start with 'mo'. This continues until we type the whole searchWord.

This approach ensures we always get three or less products with minimum lexicographical order as we are doing DFS in alphabetical order.

Now, let's see Python solution for this problem:

1
2python
3class TrieNode:
4    def __init__(self):
5        self.children = [None]*26
6        self.words = []
7
8class Solution:
9    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
10        root = TrieNode();
11        for product in sorted(products):
12            node = root
13            for c in product:
14                if node.children[ord(c)-97] == None:
15                    node.children[ord(c)-97] = TrieNode();
16                node = node.children[ord(c)-97]
17                node.words.append(product);
18        
19        suggestions = []
20        node = root
21        for c in searchWord:
22            if node != None:
23                node = node.children[ord(c)-97];
24            if node == None or len(node.words) == 0:
25                suggestions.append([]);
26            else:
27                suggestions.append(node.words[0:3]);
28            
29        return suggestions;

Here, root of TrieNode stores all products. For each character of each product, we add this product into the list of words of TrieNode of this character.

While typing searchWord, when we type a character, we can simply fetch corresponding TrieNode and add at most first three words of this TrieNode into our suggestions. If no such TrieNode exists, we add an empty suggestion.

This approach uses sorted product names and lexical order to find the minimum three products for each character of searchWord.Now, let's move on to the JavaScript solution.

For the JavaScript solution, we can use an approach similar to the one in Python. First, we'll create the Trie and then run the Depth First Search (DFS) on it.

1
2js
3class TrieNode {
4    constructor() {
5        this.children = Array.from({length: 26}, () => null);
6        this.words = [];
7    }
8}
9
10class Trie {
11    constructor() {
12        this.root = new TrieNode();
13    }
14  
15    insert(word) {
16        let node = this.root;
17        for (let c of word) {
18            let i = c.charCodeAt(0) - 97;
19            if (node.children[i] == null) {
20                node.children[i] = new TrieNode();
21            }
22            node = node.children[i];
23            node.words.push(word);
24            node.words.sort();
25            if (node.words.length > 3) {
26                node.words.pop();
27            }
28        }
29    }
30  
31    search(word) {
32        let node = this.root;
33        let res = [];
34        for (let c of word) {
35            let i = c.charCodeAt(0) - 97;
36            if (node) {
37                node = node.children[i];
38            } else {
39                res.push([]);
40                continue;
41            }
42            res.push(node ? [...node.words] : []);
43        }
44        return res;
45    }
46}
47
48var suggestedProducts = function(products, searchWord) {
49    let trie = new Trie();
50    for (let product of products) {
51        trie.insert(product);
52    }
53    return trie.search(searchWord);
54};

In this JavaScript implementation, we defined a methods insert and search in Trie class to insert product names and to fetch suggestions for searchWord respectively.

Finally, let's provide the Java solution for the problem:

1
2java
3class Solution {
4    class TrieNode {
5        TrieNode[] children;
6        List<String> suggestion = new LinkedList<>();
7
8        TrieNode(){
9            children = new TrieNode[26];
10        }
11    }
12
13    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
14        TrieNode root = new TrieNode();
15        Arrays.sort(products);
16
17        for (String p : products) {
18            insert(p, root);
19        }
20
21        return search(searchWord, root);
22    }
23
24    private void insert(String p, TrieNode root) {
25        TrieNode t = root;
26        for (char c : p.toCharArray()) {
27            if (t.children[c - 'a'] == null)
28                t.children[c - 'a'] = new TrieNode();
29            t = t.children[c - 'a'];
30            t.suggestion.add(p);
31            if (t.suggestion.size() > 3)
32                t.suggestion.pollLast(); 
33        }
34    }
35
36    private List<List<String>> search(String searchWord, TrieNode root) {
37        List<List<String>> ans = new ArrayList<>();
38        for (char c : searchWord.toCharArray()) {
39            if (root != null) 
40                root = root.children[c - 'a'];
41            ans.add(root == null ? Arrays.asList() : root.suggestion);
42        }
43
44        return ans;
45    }
46}

We use the LinkedList data structure for storing suggestions in TrieNode because LinkedList provides efficient operations for inserting and removing at the end of list. We use ArrayList in search function because searchWord can be converted to charArray directly in the for-each loop.

In summary, by using the Trie data structure and DFS, we can solve this problem within the constraints and in a time efficient manner. We covered three different implementations of the solution in Python, JavaScript, and Java, demonstrating how different programming languages can be used to solve the same problem with a similar approach.