You are given an array of strings products and a string searchWord.

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 searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

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

&nbsp;
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"]]


&nbsp;
Constraints:


	1 &lt;= products.length &lt;= 1000
	1 &lt;= products[i].length &lt;= 3000
	1 &lt;= sum(products[i].length) &lt;= 2 * 104
	All the strings of products are unique.
	products[i] consists of lowercase English letters.
	1 &lt;= searchWord.length &lt;= 1000
	searchWord consists of lowercase English letters.


class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        sorted_products = sorted(products)
        res = []
        prefix = ''
        for letter in searchWord:
            prefix += letter
            words = []
            for product in sorted_products:
                if len(words) == 3:
                    break
                if product.startswith(prefix):
                    words.append(product)
            res.append(words)        
        return res
class Solution
{
    public List<List<String>> suggestedProducts(String[] products, String searchWord)
    {
        PriorityQueue<String> pq= new PriorityQueue<String>();
        List<List<String>> res= new LinkedList<List<String>>();
        List<String> segment= new LinkedList<String>();
        for(int i=0;i<products.length;i++)
            pq.offer(products[i]);

        for(int j=0;j<searchWord.length();j++)
        {
            segment= new LinkedList<String>();
            pq= reduce(pq,searchWord.substring(0,j+1));
            PriorityQueue<String> pri= new PriorityQueue<>(pq);
            int p=0;
            while(p<pq.size()&&p<3)
            {
                segment.add(pri.poll());
                p++;
            }
            res.add(segment);
        }
        return res;
    }
    public PriorityQueue<String> reduce(PriorityQueue<String> pr, String filter)
    {
        PriorityQueue<String> p= new PriorityQueue<>();
        String s="";
        while(!pr.isEmpty())
        {
            s=pr.poll();
            if(s.startsWith(filter))
                p.add(s);
        }
        return p;
    }
}
class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        map<int, vector<string>> m;
        vector<vector<string>> res;
        for (int i = 0; i < products.size(); i++)
        {
            int j = 0;
            while (products[i][j] == searchWord[j] && j < searchWord.size())
            {
                if (m.count(j) == 0)
                {
                    vector<string> v;
                    v.push_back(products[i]);
                    m.insert(make_pair(j, v));
                }
                else
                {
                    m[j].push_back(products[i]);
                }
                j++;
            }
        }
        for (int i = 0; i < searchWord.size(); i++)
        {
            if (i < m.size())
            {
                sort(m[i].begin(), m[i].end());
                int a;
                if (3 <= m[i].size())
                {
                    a = 3;
                }
                else
                {
                    a = m[i].size();
                }
                m[i].resize(a);
                res.push_back(m[i]);
            }
            else
            {
                res.push_back({});
            }
        }
        return res;
    }
};
function TrieNode(key) {
  this.key = key
  this.parent = null
  this.children  = {}
  this.end = false
  
  this.getWord = function() {
    let output = []
    let node = this
    
    while(node !== null) {
      output.unshift(node.key)
      node = node.parent
    }
    
    return output.join('')
  }
} 

function Trie() {
  this.root = new TrieNode(null)
  
  this.insert = function(word) {
    let node = this.root
    
    for (let i = 0; i < word.length; i++) {
      if (!node.children[word[i]]) {
        node.children[word[i]] = new TrieNode(word[i])
        node.children[word[i]].parent = node
      }
      
      node = node.children[word[i]]
      
      if (i === word.length - 1) {
        node.end = true
      }
    }
  }
  
  this.findAllWords = function (node, arr) {
    if (node.end) {
      arr.unshift(node.getWord());
    }

    for (let child in node.children) {
      this.findAllWords(node.children[child], arr);
    }
  }
  
  this.find  = function(prefix) {
    let node = this.root
    let output = []

    for(let i = 0; i < prefix.length; i++) {
      if (node.children[prefix[i]]) {
        node = node.children[prefix[i]]
      } else {
        return output
      }
    }

    this.findAllWords(node, output)
    
    output.sort()

    return output.slice(0, 3)
  }
  
  this.search = function(word) {
    let node = this.root
    let output = []
    
    for (let i = 0; i < word.length; i++) {
      output.push(this.find(word.substring(0, i + 1)))
    }
    
    return output
  }
}

/**
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
var suggestedProducts = function(products, searchWord) {
  let trie = new Trie()
  
  for (let product of products) {
    trie.insert(product)
  }
  
  return trie.search(searchWord)
};
Search Suggestions System