Problem: 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:
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"].
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.
Input: products = ["havana"], searchWord = "tatiana"
Output: [[],[],[],[],[],[],[]]
Explanation: No match at all
Approach: Given this search is kind of prefix search so it's intuitive that we will use Trie. However the TrieNode will have one more field which is going to be list of sorted suggestions. We will have these suggestions at every node and we will maintain it at every insertion so that we can quickly return these suggestions. That's all!
Implementation in C#:
public class TrieNode
{
public TrieNode(char ch)
{
this.Value = ch;
this.Children = new TrieNode[26];
this.Suggestions = new List<string>();
}
public char Value {get; set;}
public TrieNode[] Children {get; set;}
public List<string> Suggestions {get; set;}
}
public class Trie
{
private const char ENDOFWORD = '#';
public Trie()
{
this.root = new TrieNode('X');
}
public void InsertWord(string word)
{
var node = this.root;
foreach (char ch in word)
{
int index = ch - 'a';
if (node.Children[index] == null)
{
node.Children[index] = new TrieNode('*');
}
node = node.Children[index];
this.AdjustSuggestions(node, word);
}
node.Value = ENDOFWORD;
}
public IList<IList<string>> GetSuggestions(string searchWord)
{
var result = new List<IList<string>>();
var node = this.root;
foreach (char ch in searchWord)
{
int index = ch - 'a';
if (node.Children[index] == null)
{
break;
}
node = node.Children[index];
result.Add(node.Suggestions);
}
int remainingElements = searchWord.Length - result.Count;
for (int i = 0; i < remainingElements; ++i)
{
result.Add(new List<string>());
}
return result;
}
private void AdjustSuggestions(TrieNode node, string word)
{
// We can do better here, instead of assuming max number of
// suggestions is 3
int count = node.Suggestions.Count;
if (count == 0)
{
node.Suggestions.Add(word);
}
else if (count == 1)
{
if (String.Compare(word, node.Suggestions[0]) < 0)
{
node.Suggestions.Insert(0, word);
}
else
{
node.Suggestions.Add(word);
}
}
else if (count == 2)
{
this.HandleTwoSuggestions(node, word);
}
else
{
if (String.Compare(word, node.Suggestions[2]) < 0)
{
node.Suggestions.RemoveAt(node.Suggestions.Count - 1);
this.HandleTwoSuggestions(node, word);
}
}
}
private void HandleTwoSuggestions(TrieNode node, string word)
{
if (String.Compare(word, node.Suggestions[0]) < 0)
{
node.Suggestions.Insert(0, word);
}
else if (String.Compare(word, node.Suggestions[1]) < 0)
{
node.Suggestions.Insert(1, word);
}
else
{
node.Suggestions.Add(word);
}
}
private TrieNode root;
}
public class Solution
{
public IList<IList<string>> SuggestedProducts(string[] products,
string searchWord)
{
var trie = new Trie();
foreach (var product in products)
{
trie.InsertWord(product);
}
return trie.GetSuggestions(searchWord);
}
}
Complexity: O(m * n + l) where m is number of products, n is length of largest string in products and l is length of search word.
No comments:
Post a Comment