Trie 3 | Leetcode 1268. Search Suggestions System | Amazon | OA 2020 | Keyword Suggestions

 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. 

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: [[],[],[],[],[],[],[]]

Solution :

class Solution {

    class TrieNode{

        TrieNode[] children=new TrieNode[26];

        LinkedList<String> suggestions=new LinkedList<>();

        boolean isEnd=false;

    }

    

    private void insert(String p,TrieNode root){

        TrieNode node=root;

        for(char ch:p.toCharArray()){

            if(node.children[ch-'a']==null){

               node.children[ch-'a']=new TrieNode(); 

            }

            node=node.children[ch-'a'];

            //add the word in the suggestions

            node.suggestions.add(p);

            Collections.sort(node.suggestions);

            

            if(node.suggestions.size() >3){

               node.suggestions.pollLast(); 

            }

        }

    }

    private List<List<String>> search(String searchWord,TrieNode root){

        List<List<String>> ans=new ArrayList<>();

        TrieNode node=root;

        for(char ch:searchWord.toCharArray()){

            if(node!=null)

                node=node.children[ch-'a'];

            ans.add(node== null ? Arrays.asList():node.suggestions);

            

        }

        return ans;

        

    }

    

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

        TrieNode root=new TrieNode();

        for(String s:products){

            insert(s,root);

        }

        return search(searchWord,root);

    }

}

Analysis:

Complexity depends on the sorting, the process of building Trie and the length of searchWord. Sorting cost time O(m * n), due to involving comparing String, which cost time O(m) for each comparison, building Trie cost O(m * n). Therefore,

Time: O(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().