Question :

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.

Sample Test Case :

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.

Approach :

This question can be approached using Trie data structure. Here we need to take care of the prefix and finding the prefix is pretty straight forward when we use Trie data structure.
In our trie data structure, we will have TrieNode array of size 26 and also a linked list of strings in order to store the top 3 suggestion according to our question.

So the Trie structure will be :

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

Enter fullscreen mode Exit fullscreen mode

Insert

We know, trie have some basic operations like insert, search etc and follow this post to have a basic idea about how we insert.

#java #algorithms #tutorial #interview

Here, we make a trick that we will add the words into the suggestion linked list and since we need only 3 words as suggestion, we delete the last word if the size of the linked list exceeds 3.

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

Enter fullscreen mode Exit fullscreen mode

Here, when ever a particular character is pressed, a new node is created if not present and add that word as suggestion into the linked list.

So after insertion of the words, we will be having
a structure like this :

Search

Now its quite simple, we go through each every character inside the searchWord, looks the respective node of that character and add the suggestion on to the result. If the character is not having any node on our trie, then we add empty value into our result.

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

Enter fullscreen mode Exit fullscreen mode

Full Code :

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

Enter fullscreen mode Exit fullscreen mode

Complexity :

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().

Rohithv07 / LeetCode

LeetCode problems that are solved.

LeetCode

LeetCode problems that are solved.

• take the bit of the ith(from right) digit:

  bit = (mask >> i) & 1;

• set the ith digit to 1: mask = mask | (1 << i);

• set the ith digit to 0: mask = mask & (~(1 << i));

View on GitHub

原文链接：Leetcode 1268 : Search Suggestions System (Trie Approach)