1268. Search Suggestions System

/**

 * 1268. Search Suggestions System

 * 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.

 *

 * 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”]

*/

See the code for this problem here at github : https://github.com/zcoderz/leetcode/blob/main/src/main/java/amazon/medium/SearchSuggestionSystem.java

Observation: The question is asking for three words that match the characters specified in the search word. This is a simple practice question that can be easily answered via a trie.

Logic:

1. Build a Trie using the collection of words supplied
2. For each substring of the search word start from first index to the last index
   1. Traverse the trie using the substring
   1. Once you traverse the trie until end of the substring
      1. Find up to 3 words that have prefix starting from string in b
      1. This is done by traversing the trie until 3 words are found

Here is the code:

public List<List<String>> suggestedProducts(String[] products, String searchWord) {

    TrieNode node = new TrieNode();
    node.buildTrie(products);
    List<List<String>> list = new ArrayList<>();
    for (int i = 1; i <= searchWord.length(); i++) {
        String str = searchWord.substring(0, i);
        list.add(search(node, 0, str));
    }
    return list;
}

private List<String> search(TrieNode node, int index, String word) {
    if (index == word.length()) {
        List<String> list = new ArrayList<>(3);
        getThreeWordsFrom(node, list);
        return list;
    }
    TrieNode childNode = node.getChildNode(word.charAt(index));
    if (childNode == null) {
        return new ArrayList<>();
    }
    return search(childNode, index + 1, word);
}

void getThreeWordsFrom(TrieNode node, List<String> list) {
    if (list.size() == 3) {
        return;
    }
    if (node.getWord() != null) {
        list.add(node.getWord());
    }
    for (TrieNode childNode : node.getAllChildNodes().values()) {
        getThreeWordsFrom(childNode, list);
        if (list.size() == 3) {
            return;
        }
    }
}