Search Suggestions System

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.

Examples

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.

Solution

To solve this problem, we need to return a list of up to three lexicographically smallest product names that match the prefix formed by the characters typed so far in searchWord.

Method 1 - Using 2 lists and sorting

Here is the approach:

1. Sorting the Products: Since we need lexicographically smallest products, we start by sorting the products array.

2. Prefix Matching: For each character typed in searchWord, we can iteratively match all product names to find the ones that start with the prefix formed so far.

3. Iterative Filtering:

   • Build the prefix incrementally.
   • Filter the sorted product list for names matching the prefix.
   • Store at most three matches in the result.

4. Use binary search techniques (if applicable for optimisation) or iterate through the array for prefix matching.

Code

Java

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> ans = new ArrayList<>();
        Arrays.sort(products);
        String prefix = "";
        for (char ch : searchWord.toCharArray()) {
            prefix += ch;
            List<String> matches = new ArrayList<>();
            for (String p : products) {
                if (p.startsWith(prefix)) {
                    matches.add(p);
                    if (matches.size() == 3) break; // limit results to 3
                }
            }
            ans.add(matches);
        }
        return ans;
    }
}

Python

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        ans: List[List[str]] = []
        products.sort()
        prefix: str = ""
        for ch in searchWord:
            prefix += ch
            matches: List[str] = [p for p in products if p.startswith(prefix)]
            ans.append(matches[:3])  # limit to 3 results
        return ans

Complexity

• ⏰ Time complexity: O(n * log(n) + m * n)
  • Sorting the products: O(n * log(n)), where n is the length of products.
  • For each prefix, filtering through products: O(n * m), where m is the length of searchWord. So total complexity is approximately O(n * log(n) + m * n).
• 🧺 Space complexity: O(n)

Method 2 - Using Trie

Using a Trie data structure can significantly optimise prefix matching in this problem. Here's the reasoning, approach, and implementation for solving it with a Trie.

Reasoning

A Trie is a tree-based data structure used for efficiently storing strings. Each node represents a character. Using a Trie, we can:

1. Quickly insert products into the structure with their prefixes.
2. Efficiently find all product names matching a prefix by traversing nodes.

We will preprocess the products list into a Trie, then for each prefix formed by searchWord, perform a traversal to obtain at most three lexicographically smallest suggestions.

Approach

1. Build the Trie:

   • Construct the Trie using products.
   • Each node contains a list of references to at most three lexicographically smallest products at that prefix.

2. Query the Trie for Prefix Suggestions:

   • For each prefix created by typing characters in searchWord, traverse the Trie to find suggested products.

3. Suggestion Limitation:

   • While constructing the Trie and storing products at each node, maintain only the first three lexicographically smallest product names.

Code

Java

class Solution {
    class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        List<String> suggestions = new ArrayList<>();
    }
    
    private void insertProduct(TrieNode root, String product) {
        TrieNode current = root;
        for (char ch : product.toCharArray()) {
            current.children.putIfAbsent(ch, new TrieNode());
            current = current.children.get(ch);
            
            // Maintain at most 3 lexicographical suggestions at each node
            if (current.suggestions.size() < 3) {
                current.suggestions.add(product);
            }
        }
    }
    
    private List<String> searchSuggestions(TrieNode root, String prefix) {
        TrieNode current = root;
        for (char ch : prefix.toCharArray()) {
            current = current.children.get(ch);
            if (current == null) {
                return new ArrayList<>();
            }
        }
        return current.suggestions;
    }
    
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        TrieNode root = new TrieNode();
        Arrays.sort(products); // Sort products lexicographically
        
        // Construct the Trie
        for (String product : products) {
            insertProduct(root, product);
        }
        
        List<List<String>> result = new ArrayList<>();
        String prefix = "";
        
        // Query the Trie for each prefix in searchWord
        for (char ch : searchWord.toCharArray()) {
            prefix += ch;
            result.add(searchSuggestions(root, prefix));
        }
        
        return result;
    }
}

Python

class TrieNode:
    def __init__(self):
        self.children: dict[str, TrieNode] = {}
        self.suggestions: list[str] = []

class Solution:
    def insertProduct(self, root: TrieNode, product: str) -> None:
        current = root
        for ch in product:
            if ch not in current.children:
                current.children[ch] = TrieNode()
            current = current.children[ch]
            
            # Maintain at most 3 lexicographical suggestions at each node
            if len(current.suggestions) < 3:
                current.suggestions.append(product)
    
    def searchSuggestions(self, root: TrieNode, prefix: str) -> List[str]:
        current = root
        for ch in prefix:
            if ch not in current.children:
                return []
            current = current.children[ch]
        return current.suggestions
    
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        root = TrieNode()
        products.sort()  # Sort products lexicographically
        
        # Construct the Trie
        for product in products:
            self.insertProduct(root, product)
        
        result: List[List[str]] = []
        prefix: str = ""
        
        # Query the Trie for each prefix in searchWord
        for ch in searchWord:
            prefix += ch
            result.append(self.searchSuggestions(root, prefix))
        
        return result

Complexity

• Time: O(n * l + m * k)
  • Building the Trie: O(n * l), where n is the number of products and l is their average length.
  • Querying the Trie: O(m * k), where m is the length of searchWord, and k is the branching factor at each prefix (limited to 3 products stored per node).
  • Total: Approximately O(n * l + m * k).
• Space: O(n * l). The Trie requires O(n * l) space for storing the products and associated nodes, where l is the average length of products.