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<>();
}
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.
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();
}
}
}
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;
}
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<>();
}
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().
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));
Top comments (2)
"Building Trie cost time O(m * m * n)"
This statement is incorrect. Building is O(m * n). And search is O(m).
So total is O(m * n) + O(m) ; which is eventually O(m * n)
And space complexity is O ( 24 * 3 * m ) => O(m)
Thank you for the feedback, I will really have a look into this.