1268-search-suggestions-system.js

/**
 * Binary Search
 * 
 * Time O(n*log(n) + m*n) | Space O(m)
 * https://leetcode.com/problems/search-suggestions-system/description/
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
var suggestedProducts = function(products, searchWord) {

    products.sort((product1, product2) => {
        if(product1 < product2) {
            return -1;
        }
        if(product2 < product1) {
            return 1;
        }
        if(product1 === product2) {
            return 0;
        }
    });

    const result = [];
    let left = 0;
    let right = products.length - 1;
    for(let i = 0;  i < searchWord.length; i++) {
        let char = searchWord[i];
        
        while(left <= right && (products[left].length - 1 < i || products[left][i] !== char)) {
            left++;
        }
        while(left <= right && (products[right].length - 1 < i || products[right][i] !== char)) {
            right--;
        }

        const subResult = [];
        const len = Math.min(right - left + 1, 3);
        for(let j = 0; j < len; j++) {
            subResult.push(products[left+j]);
        }
        result.push(subResult);
    }

    return result;
};

/**
 * DFS - Trie
 * Time O(N * M) | Space O(N)
 * https://leetcode.com/problems/search-suggestions-system/
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
var suggestedProducts1 = (products, searchWord) => new Trie()
    .buildTrie(products)
    .searchWord(searchWord);

class Node {
    constructor () {
        this.children = new Map();
        this.isWord = false;
    }
};

class Trie {
    constructor () {
        this.root = new Node();
    }

    buildTrie (products) {
        for (const word of products) {
            this.insert(word);
        }

        return this;
    }
    
    insert (word, { root: node } = this) {        
        for (const char of word.split('')) {
            const child = (node.children.get(char) ?? new Node());
            
            node.children.set(char, child);

            node = child;
        }

        node.isWord = true;
    }
    
    searchWord (searchWord, buffer = [], suggestions = []) {
        for (const char of searchWord.split('')) {
            const prefix = this.getPrefix(buffer, char);
            const words = this.getSuggestions(prefix);

            suggestions.push(words);
        }
        
        return suggestions;
    }

    getPrefix (buffer, char) {
        buffer.push(char);

        return buffer.join('');
    }
    
    getSuggestions (prefix, words = []) {
        const node = this.getPrefixNode(prefix);

        const isInvalidPrefix = (node === null);
        if (isInvalidPrefix) return words
        
        return this.search(node, prefix, words);
    }

    getPrefixNode (prefix, { root: node } = this) {
        for (const char of prefix.split('')) {
            const child = (node.children.get(char) ?? null);

            const isLeafNode = (child === null);
            if (isLeafNode) return null;

            node = child;
        }

        return node;
    }

    search (node, word, words) {
        const isBaseCase = (words.length === 3);
        if (isBaseCase) return words;

        if (node.isWord) words.push(word);

        return this.dfs(node, word, words);
    }

    dfs (node, word, words) {
        for (const char of this.getChars()) {
            const child = (node.children.get(char) ?? null);

            const isLeafNode = (child === null);
            if (isLeafNode) continue;
        
            this.search(child, (word + char), words);
        }

        return words;
    }

    getChars () {
        return new Array(26).fill()
            .map((_, index) => String.fromCharCode((index + 97)));
    }
};