Vultr DocsLatest Content

Search Suggestions System

Updated on 10 July, 2025
Search Suggestions System header image

Problem Statement

In this task, you're provided with an array of strings named products which represents different items, and a single string named searchWord which simulates the act of a user typing to search for a particular product. The system needs to suggest, at most, three product names from the products list that begin with the prefix provided by each sequential character added from searchWord. The products returned must be the first three lexicographically smallest matches. If there are more than three matches, the system should still only return the first three in lexicographical order. Your job is to develop a system that constructs a list of lists containing the suggested products after each character of the searchWord is entered.

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.

Constraints

  • 1 <= products.length <= 1000
  • 1 <= products[i].length <= 3000
  • 1 <= sum(products[i].length) <= 2 * 104
  • All the strings of products are unique.
  • products[i] consists of lowercase English letters.
  • 1 <= searchWord.length <= 1000
  • searchWord consists of lowercase English letters.

Approach and Intuition

The problem requires us to simulate an auto-complete feature commonly seen in search functionalities, which involves matching string prefixes and ordering. Here is a step-by-step approach to solving the problem:

  1. Sort the products list: Sorting the products arrays lexicographically ensures that when we select the top three matches, they are the smallest lexicographically. This sorting needs to be done only once.

  2. Sequential Prefix Matching: For each character addition to the searchWord, generate the current prefix of the searchWord and match it against the products.

  3. Collecting up to Three Matches: As the prefixes are generated:

    • Iterate over the sorted products list.
    • Check if the product starts with the current prefix.
    • If it does, add it to the current list of results for that prefix iteration.
    • Stop once three matching products are found or the products list is exhausted.

  4. Form the Result List: For each prefix derived from searchWord, store the matches (up to three) in a list, which in turn will be stored in an overall result list. This list should be the final output, match the expected structure.

Example Breakdown

From Example 1:

  • For prefix "m": The matches are ["mobile","moneypot","monitor"], and all are suggested as they are the first three lexicographically smallest.
  • For prefix "mo": Same top three matches apply as for "m".
  • For "mou": At this point, the valid matches switch to ["mouse", "mousepad"] as these are the only two that start with "mou".

This parameter helps in narrowing down the options the user is presented as they type more characters, improving their search experience by refining options.

Solutions

  • C++
cpp 
// Custom autocomplete system using Trie
class AutocompleteSystem
{
    // Structure for the Trie's node
    struct Node {
        bool endsWord = false;
        vector<Node *> links{vector<Node *>(26, NULL)};
    } * trieRoot, *travel;
    
    // Helper method to execute deep search with the current prefix
    void searchWithPrefix(Node * travel, string & currentWord, vector<string> & output) {
        if (output.size() == 3)
            return;
        if (travel->endsWord)
            output.push_back(currentWord);
    
        for (char ch = 'a'; ch <= 'z'; ch++)
            if (travel->links[ch - 'a']) {
                currentWord += ch;
                searchWithPrefix(travel->links[ch - 'a'], currentWord, output);
                currentWord.pop_back();
            }
    }
    
public:
    AutocompleteSystem() {
        trieRoot = new Node();
    }
    // Method to insert new word into the Trie
    void addWord(string & word) {
        travel = trieRoot; // Start from root
        for (char &ch : word) {
            if (!travel->links[ch - 'a'])
                travel->links[ch - 'a'] = new Node();
            travel = travel->links[ch - 'a'];
        }
        travel->endsWord = true; // Mark the node as end of the word
    }
    // Retrieve list of up to three words with common prefix
    vector<string> fetchStartingWith(string & prefix) {
        travel = trieRoot;
        vector<string> output;
    
        for (char &ch : prefix) {
            if (!travel->links[ch - 'a'])
                return output; // Exit if the prefix doesn't exist
            travel = travel->links[ch - 'a'];
        }
        searchWithPrefix(travel, prefix, output);
        return output;
    }
};
class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string> &products,
                                             string searchWord) {
        AutocompleteSystem system=AutocompleteSystem();
        vector<vector<string>> suggestions;
    
        // Load all products into the AutocompleteSystem
        for(string &p:products)
            system.addWord(p);
        string currentPrefix;
        for (char &ch : searchWord) {
            currentPrefix += ch;
            suggestions.push_back(system.fetchStartingWith(currentPrefix));
        }
        return suggestions;
    }
};

The provided C++ code implements a custom autocomplete system using a Trie data structure and two principal classes: AutocompleteSystem and Solution. Here's a breakdown of the functionalities and structure of this code.

AutocompleteSystem:

  • Trie Node Definition: Each node has a flag to indicate if a word ends and an array of pointers for each letter of the alphabet.
  • addWord Method: Adds a new word to the Trie, marking the end of the word and creating any necessary nodes.
  • fetchStartingWith Method: Returns up to three suggestions based on a given prefix. It navigates through the Trie following the prefix letters; if found, it then fetches suggestions using a helper method.
  • searchWithPrefix Helper Method: Performs a depth-first search from the current node to gather suggestions. The search halts when three suggestions are gathered or there are no further nodes to explore.

Solution:

  • suggestedProducts Method: Uses the AutocompleteSystem to suggest products. It loads all product names into the Trie, then iteratively builds prefixes from the search word, collecting up to three suggestions for each prefix.

To use this system:

  1. Instantiate an AutocompleteSystem.
  2. Load the system with a set of predefined words using addWord.
  3. For each successive character in the query string, fetch and accumulate suggestions using fetchStartingWith.

This implementation is efficient for repeatedly suggesting completions in real-time and optimizes searching using Trie's structure, which significantly reduces lookup time compared to linear search methods. The systematic organization using methods for adding words and fetching suggestions based on prefixes provides a clear and maintainable structure.

  • Java
java 
class AutoCompleteSystem {
    
    class TrieNode {
        boolean terminates = false;
        List<TrieNode> links = Arrays.asList(new TrieNode[26]);
    }
        
    TrieNode root, nodePointer;
    List<String> searchResults;
    
    void depthFirstSearch(TrieNode node, String prefix) {
        if (searchResults.size() == 3)
            return;
        if (node.terminates)
            searchResults.add(prefix);
    
        for (char ch = 'a'; ch <= 'z'; ch++)
            if (node.links.get(ch - 'a') != null)
                depthFirstSearch(node.links.get(ch - 'a'), prefix + ch);
    }
        
    AutoCompleteSystem() {
        root = new TrieNode();
    }
    
    void addWord(String word) {
        nodePointer = root;
        for (char ch : word.toCharArray()) {
            if (nodePointer.links.get(ch - 'a') == null)
                nodePointer.links.set(ch - 'a', new TrieNode());
            nodePointer = nodePointer.links.get(ch - 'a');
        }
        nodePointer.terminates = true;
    }
        
    List<String> searchPrefix(String prefix) {
        nodePointer = root;
        searchResults = new ArrayList<>();
        for (char ch : prefix.toCharArray()) {
            if (nodePointer.links.get(ch - 'a') == null)
                return searchResults;
            nodePointer = nodePointer.links.get(ch - 'a');
        }
        depthFirstSearch(nodePointer, prefix);
        return searchResults;
    }
};
    
class Solution {
    List<List<String>> suggestedProducts(String[] products, String searchKeyword) {
        AutoCompleteSystem trie = new AutoCompleteSystem();
        List<List<String>> autocompleteResults = new ArrayList<>();
        for (String product : products)
            trie.addWord(product);
        String currentPrefix = "";
        for (char ch : searchKeyword.toCharArray()) {
            currentPrefix += ch;
            autocompleteResults.add(trie.searchPrefix(currentPrefix));
        }
        return autocompleteResults;
    }
};

This Java-based solution implements an autocomplete system using a Trie data structure to handle suggestions for product searches efficiently. The main class, AutoCompleteSystem, includes methods to add words to the Trie and search for prefixes.

  • The TrieNode inner class represents each node in the Trie. It has a boolean terminates to signify the end of a word, and a List of TrieNode links corresponding to each character in the alphabet.
  • The constructor initializes the root of the Trie.
  • addWord method iterates through each character of the word, traverses the Trie, and sets up new nodes as needed. It marks the end of a word by setting terminates to true.
  • depthFirstSearch recursively searches through the Trie to find all complete words that start with a given prefix. This method ensures only up to three results are added to maintain the required suggestion limit.
  • searchPrefix looks up a specific prefix in the Trie. It checks each character of the prefix to navigate through the Trie and then uses depthFirstSearch to gather completions.

The Solution class contains suggestedProducts, which manages the Trie's operations based on a list of product names and a search keyword. It processes the search keyword character by character, growing the search prefix iteratively. For each prefix formed, it retrieves suggestions using the AutoCompleteSystem instance.

  • Call addWord for each product to construct the Trie.
  • For each character in the search keyword, extend the current prefix, and retrieve suggestions based on this prefix. Add these suggestions to the list of autocomplete results.

The application of Trie here allows for efficient insertion and search operations, which is crucial for quickly accessing potential suggestions as the user types each character of their query. Use this system to improve the responsiveness and performance of product searches in applications.

Comments

No comments yet.