JS | Auto-complete feature using Trie | Search Suggestions System | Coding Round Interview Question

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.

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

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

The idea,

• Sorting Simple Traversal
• Trie + DFS

Sort | Simple Traversal

1. Sort the products
2. Keep filtering products that match our input

var suggestedProductsSort = function(products, searchWord) {
    products.sort();
    let res = [];
    for (let i=0; i< searchWord.length; i++) {
        products = products.filter( (p) => p[i] == searchWord[i]);
        res.push(products.slice(0, 3));
    }
    return res;
}

Trie + DFS

1. Create a Trie from the given products input.
2. Iterate each character of the searchWord adding it to the prefix to search for.
3. After adding the current character to the prefix traverse the trie pointer to the node representing prefix.
4. Now traverse the tree from curr pointer in a preorder fashion and record whenever we encounter a complete word.
5. Limit the result to 3 and return dfs once reached this limit.
6. Add the words to the final result.

Adding a word “mouse”, “money” to TRIE,

Adding word “mouse”, “money” to TRIE,

/**
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
var suggestedProducts = function (products, searchWord) {

    products.sort();

    function Trie() {
        this.children = {};
    }

    Trie.prototype.addWord = function (word) {
        let current = this;

        for (let i = 0; i < word.length; i++) {
            const char = word.charAt(i);

            if (!current.children[char]) {
                current.children[char] = new Trie();
            }
            current = current.children[char];
        }

        current.word = word;
    }

    let trie = new Trie();

    for (const product of products) {
        trie.addWord(product);
    }

    const output = [];
    for (let i = 0; i < searchWord.length; i++) {
        const char = searchWord.charAt(i);
        trie = !!trie ? trie.children[char] : null;
        output.push(!!trie ? dfs(trie) : []);
    }

    return output;

    function dfs(node, output = []) {
        if (!!node.word) {
            output.push(node.word);
        }

        for (const child in node.children) {
            dfs(node.children[child], output)
        }

        return output.length >= 3 ? output.slice(0, 3) : output;
    }

};

Follow me for more coding interview.

This problem is very popular in the coding interviews.

Keep learning, keep growing!

Don’t forget to follow me for more such articles, and subscribe to our newsletter.

Let’s connect on LinkedIn!. Please read more for more data structure javascript question.

Reference :

• https://www.geeksforgeeks.org/trie-insert-and-search/