Trie Variation

-
Here is the problem: https://leetcode.com/problems/search-suggestions-system/
1268. Search Suggestions System
Medium
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. 

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.
Trie fits well for this problem, with a simple variation: the keys should be sorted. Hence instead of using a simple Hash Map to stored the nodes of the trie, change it to a Sorted Dictionary. The main implementation is here where the key is to systematically cover all the base cases, and the induction will leverage the fact that keys are sorted which will generate the desired lexicographic order, this is the for loop that does so. Slow, but enough to pass. Cheers, ACC.

public class Trie
{
    private SortedDictionary<char, Trie> sd = null;
    private bool endOfWord = false;
    public Trie()
    {
        sd = new SortedDictionary<char, Trie>();
        endOfWord = false;
    }

    public void Insert(string word)
    {
        if (String.IsNullOrEmpty(word)) this.endOfWord = true;
        else if (sd.ContainsKey(word[0])) (sd[word[0]]).Insert(word.Substring(1));
        else
        {
            Trie newTrie = new Trie();
            sd.Add(word[0], newTrie);
            (sd[word[0]]).Insert(word.Substring(1));
        }
    }

    public void SearchMaxMatches(string searchWord,
                                    string currentWord,
                                    int MAX,
                                    ref int numberMatches,
                                    List<string> matches)
    {
        if (numberMatches >= MAX) return;
        if (!String.IsNullOrEmpty(searchWord) && !sd.ContainsKey(searchWord[0])) return;
        if (!String.IsNullOrEmpty(searchWord) && sd.ContainsKey(searchWord[0]))
        {
            sd[searchWord[0]].SearchMaxMatches(searchWord.Substring(1), currentWord + searchWord[0].ToString(), MAX, ref numberMatches, matches);
            return;
        }

        //Searchword is empty
        if (endOfWord)
        {
            matches.Add(currentWord);
            numberMatches++;
        }
        foreach (char key in sd.Keys)
        {
            sd[key].SearchMaxMatches(searchWord, currentWord + key.ToString(), MAX, ref numberMatches, matches);
        }
    }
}

public class Solution
{
    public IList<IList<string>> SuggestedProducts(string[] products, string searchWord)
    {
        Trie trie = new Trie();
        foreach (string product in products) trie.Insert(product);

        List<IList<string>> retVal = new List<IList<string>>();
        for (int i = 1; i <= searchWord.Length; i++)
        {
            List<string> matches = new List<string>();
            int numberMatches = 0;
            trie.SearchMaxMatches(searchWord.Substring(0, i), "", 3, ref numberMatches, matches);
            retVal.Add(matches);
        }

        return retVal;
    }
}

Comments

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more