Sponsored
Sponsored
This approach involves sorting the products array first and then iteratively constructing prefixes from the searchWord. For each prefix, use a simple linear search over the sorted products array to find matches. By keeping the products sorted, it ensures that we can easily pick the smallest lexicographical options.
After sorting, for every prefix of the searchWord, we traverse the sorted products list, check if the product starts with the current prefix, and collect up to three matches.
Time Complexity: O(n log n) due to sorting, where n is the length of products. Each prefix search is O(n), leading to an overall complexity of O(n log n + m * n), where m is the length of searchWord.
Space Complexity: O(1) additional space is needed outside the result storage, although storing results may take O(m * 3) space.
1using System;
2using System.Collections.Generic;
3
4class SearchSuggestions {
5 public IList<IList<string>> SuggestedProducts(string[] products, string searchWord) {
6 Array.Sort(products);
7 List<IList<string>> result = new List<IList<string>>();
8 string prefix = string.Empty;
9 foreach (char c in searchWord) {
10 prefix += c;
11 List<string> matches = new List<string>();
12 foreach (string product in products) {
13 if (product.StartsWith(prefix)) {
14 matches.Add(product);
15 if (matches.Count == 3) break;
16 }
17 }
18 result.Add(matches);
19 }
20 return result;
21 }
22
23 static void Main() {
24 string[] products = {"mobile","mouse","moneypot","monitor","mousepad"};
25 string searchWord = "mouse";
26 SearchSuggestions ss = new SearchSuggestions();
27 var result = ss.SuggestedProducts(products, searchWord);
28 foreach (var list in result) {
29 Console.WriteLine(string.Join(" ", list));
30 }
31 }
32}This C# code involves sorting products first and then generating the prefix from searchWord to filter products. It adds up to three matching results, ensuring lexicographical order due to the initial sort.
This approach aims at using a Trie to efficiently handle prefix matching. With a Trie, we insert all product names into the Trie. As each character is typed in the searchWord, we traverse the Trie to check for the top three lexicographical matches.
Using a Trie allows us to handle the prefix matching efficiently by navigating through the structure step by step according to the current prefix.
Time Complexity: O(n m) to insert all products (where n is number of products and m is max product length), and O(k) to search for each prefix (where k is the length of searchWord).
Space Complexity: O(n m) for the Trie storage, since we store each character of every word.
1using System.Collections.Generic;
class TrieNode {
public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
public List<string> Suggestions = new List<string>();
}
class Solution {
public void Insert(string product, TrieNode node) {
foreach (char c in product) {
if (!node.Children.ContainsKey(c)) {
node.Children[c] = new TrieNode();
}
node = node.Children[c];
if (node.Suggestions.Count < 3) {
node.Suggestions.Add(product);
}
}
}
public IList<IList<string>> SuggestedProducts(string[] products, string searchWord) {
Array.Sort(products);
TrieNode root = new TrieNode();
foreach (string product in products) {
Insert(product, root);
}
List<IList<string>> result = new List<IList<string>>();
TrieNode node = root;
foreach (char c in searchWord) {
if (node != null) {
node = node.Children.ContainsKey(c) ? node.Children[c] : null;
}
result.Add(node != null ? new List<string>(node.Suggestions) : new List<string>());
}
return result;
}
static void Main() {
string[] products = {"mobile","mouse","moneypot","monitor","mousepad"};
string searchWord = "mouse";
Solution solution = new Solution();
var result = solution.SuggestedProducts(products, searchWord);
foreach (var list in result) {
Console.WriteLine(string.Join(" ", list));
}
}
}Using a Trie, this C# implementation tracks each node with appropriate top three suggestions. Nodes correspond to characters in product names. We then fetch results by prefix, using the Trie to index.