1268.Search_Suggestions_System(Medium).md

1268. Search Suggestions System (Medium)

Date and Time: Aug 15, 2024, 11:23 (EST)

Link: https://leetcode.com/problems/search-suggestions-system/

Question:

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"

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"]]

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 * 10^4

• All the strings of products are unique.

• products[i] consists of lowercase English letters.

• 1 <= searchWord.length <= 1000

• searchWord consists of lowercase English letters.

Walk-through:

1. Same as previous Tries questions, we add all word from products into Trie with self.words[], self.n to save three words at each node with n. While n < 3, we appending the sorted(products) for word we add, then n += 1.

2. We use TrieNode.search() to return a list or result. It appends each c from searchWord's words into res.

Note we have to break in search() instead of adding [] in the else case, because if we do that, it will append [] for the mismatch character, but if they have match character later, they will continue.

Python Trie Solution:

class TrieNode():
    def __init__(self):
        self.children = {}
        self.words = []   # Words to store all word at node
        self.n = 0
    
    def add(self, word):
        curr = self
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
            if curr.n < 3:
                curr.words.append(word)
                curr.n += 1
        
    def search(self, searchWord):
        curr = self
        res = []
        for c in searchWord:
            if c in curr.children:
                curr = curr.children[c]
                res.append(curr.words)
            else:
                break
        while len(res) < len(searchWord):
            res.append([])
        return res

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        root = TrieNode()
        products.sort()
        for product in products:
            root.add(product)
        
        return root.search(searchWord)

Time Complexity: $O(w * l)$, w is the number of words, l is the length of maximum word.
Space Complexity: $O(\text{len(all characters of all words)})$

Python Two Pointers Solution:

For two pointers method, we also need to sort products first. Then we set l, r at the beginning and the end of products, and we start looping searchWord and check condition if l, r are in bound, if current products[l] or products[r] has index i, and if searchWord[i] is the same as products[l][i] and products[r][i], otherwise, we increment l or decrement r.

Finally, we first res.append([]) prevent the case when we have no corresponding product name, and we compare min(3, remain) to make sure we append at most remain or 3 to res[-1], res[-1] will be empty if we have no corresponding product names found.

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort()
        res = []
        l, r = 0, len(products)-1
        for i in range(len(searchWord)):
            while l <= r and (len(products[l]) <= i or products[l][i] != searchWord[i]):
                l += 1
            while l <= r and (len(products[r]) <= i or products[r][i] != searchWord[i]):
                r -= 1
            res.append([])
            remain = r - l + 1
            for j in range(min(3, remain)):
                res[-1].append(products[l + j])
        return res

Time Complexity: $O(nlog\ n + mlog\ m)$, n is the number of words, m is the max length of word. Because we perform binary search on n and length of word.
Space Complexity: $O(1)$