Algorithm

Problem Name: 1268. Search Suggestions System

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.

Example 1:

```Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
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"]]
Explanation: The only word "havana" will be always suggested while typing the search word.
```

Constraints:

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

Code Examples

#1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List> suggestedProducts(String[] products, String searchWord) {
TrieNode root = new TrieNode();
for (String prod : products) {
TrieNode curr = root;
for (char c : prod.toCharArray()) {
if (curr.children[c - 'a'] == null) {
curr.children[c - 'a'] = new TrieNode();
}
curr = curr.children[c - 'a'];
}
}
List> result = new ArrayList<>();
TrieNode curr = root;
for (char c : searchWord.toCharArray()) {
if (curr == null) {
} else {
if (curr.children[c - 'a'] == null) {
curr = null;
} else {
curr = curr.children[c - 'a'];
PriorityQueue currMatchingProductsQueue = new PriorityQueue<>(curr.matchingProducts);
List currMatchingProducts = new ArrayList<>();
while (!currMatchingProductsQueue.isEmpty() && currMatchingProducts.size() < 3) {
}
}
}
}
return result;
}

private class TrieNode {
TrieNode[] children;
PriorityQueue matchingProducts;

public TrieNode() {
this.children = new TrieNode[26];
this.matchingProducts = new PriorityQueue<>();
}
}
}
``````
Copy The Code &

Input

cmd
products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"

Output

cmd

#2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const suggestedProducts = function(products, searchWord) {
products.sort()
let res = [], left = 0, right = products.length - 1
for (let i = 0; i < searchWord.length; i++) {
let c = searchWord.charAt(i), tmp = []
while (products[left]?.charAt(i) < c) left++
while (products[right]?.charAt(i) > c) right--
for (let j = 0; j < 3 && left + j <= right; j++) tmp.push(products[left+j])
res.push(tmp)
}
return res
};
``````
Copy The Code &

Input

cmd
products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"

Output

cmd

#3 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _1268_SearchSuggestionsSystem
{
public IList> SuggestedProducts(string[] products, string searchWord)
{
Array.Sort(products);
var root = new TrieNode();
foreach (string prod in products)
{
var curr = root;
foreach (char c in prod)
{
if (curr.Children[c - 'a'] == null)
curr.Children[c - 'a'] = new TrieNode();

curr = curr.Children[c - 'a'];

if (curr.Suggestion.Count < 3)
}
}

List> res = new List>();
TrieNode curr2 = root;
foreach (char c in searchWord)
{
if (curr2 != null)
curr2 = curr2.Children[c - 'a'];

res.Add(curr2 == null ? new List() : curr2.Suggestion);
}

return res;
}

private class TrieNode
{
public List Suggestion;
public TrieNode[] Children;

public TrieNode()
{
Suggestion = new List();
Children = new TrieNode[26];
}
}
}
}
``````
Copy The Code &

Input

cmd
products = ["havana"], searchWord = "havana"

Output

cmd
[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]